A share-a-ride problem (SARP), which integrates the transportation of both passengers and parcels by the ride-hailing platforms such as Uber and Lyft, has drawn considerable attention. This work introduces a novel share-a-ride problem with flexible pick-up and drop-off points (SARP-FUO) with the objectives of maximizing the total revenue of the ride-hailing platforms and minimizing the total travel distance of vehicles. A mixed integer programming model is developed to formulate SARP-FUO. Then, a knowledge-based multi-objective brain storm optimization algorithm (KM-BSO) is proposed to solve it. Two knowledge-based local search operators are specifically designed to enhance the exploration capability of KM-BSO for identifying potential nondominated solutions. The first operator employs a dynamic programming algorithm to readjust pick-up and drop-off points, while the second modifies vehicle routes based on four derived properties. Extensive experiments are conducted to compare KM-BSO with nondominated sorting genetic algorithm II, multi-objective evolutionary algorithm based on decomposition, multi-objective artificial bee colony algorithm, and a mathematical programming solver CPLEX. The results and statistical analysis demonstrate the superiority of the proposed approach in solving the studied problem. Finally, a sensitivity analysis is performed with and without flexible pick-up and drop-off points, demonstrating the advantages of the proposed model in developing intelligent public transportation systems.

Detecting critical nodes in sparse graphs is important in a variety of application domains, such as network vulnerability assessment, epidemic control, and drug design. The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. Due to its general NP-hard nature, state-of-the-art CNP solutions are based on heuristic approaches. Domain knowledge and trial-and-error are usually required when designing such approaches, thus consuming considerable effort and time. This work proposes a feature importance-aware graph attention network for node representation and combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time. It does not need any problem-specific knowledge or labeled datasets as required by most of existing methods. Once the model is trained, it can be generalized to cope with various types of CNPs (with different sizes and topological structures) without re-training. Computational experiments on 28 real-world networks show that the proposed method is highly comparable to state-of-the-art methods. It does not require any problem-specific knowledge and, hence, can be applicable to many applications including those impossible ones by using the existing approaches. It can be combined with some local search methods to further improve its solution quality. Extensive comparison results are given to show its effectiveness in solving CNP.Note to Practitioners—This work is motivated by the problems of identifying influential nodes from a sparse graph or network. Various practical applications can be naturally modeled as critical node problems, e.g., finding the most influential stations or airports within a transportation network, identifying a specific number of people to be vaccinated in order to reduce the overall transmissibility of a virus, and reinforcing the protection over some most important nodes to make the electric network more stable. It proposes an effective end-to-end deep learning algorithm to solve the critical node problem. The proposed approach combines feature importance-aware graph attention network with dueling double deep Q-network. Extensive numerical experiments and comparisons show that our proposed algorithm is highly comparable to state-of-the-art algorithms and can help decision-makers to discover valuable knowledge or influential nodes in a real-world network.

Pioneer researches recognize evidences as crucial elements in fake news detection apart from patterns. Existing evidence-aware methods either require laborious pre-processing procedures to assure relevant and high-quality evidence data, or incorporate the entire spectrum of available evidences in all news cases, regardless of the quality and quantity of the retrieved data. In this paper, we propose an approach named SEE that retrieves useful information from web-searched annotation-free evidences with an early-termination mechanism. The proposed SEE is constructed by three main phases: Searching online materials using the news as a query and directly using their titles as evidences without any annotating or filtering procedure, sequentially Examining the news alongside with each piece of evidence via attention mechanisms to produce new hidden states with retrieved information, and allowing Early-termination within the examining loop by assessing whether there is adequate confidence for producing a correct prediction. We have conducted extensive experiments on datasets with unprocessed evidences, i.e., Weibo21, GossipCop, and pre-processed evidences, namely Snopes and PolitiFact. The experimental results demonstrate that the proposed method outperforms state-of-the-art approaches.

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0019 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0019 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

This study considers a well-known critical node detection problem that aims to minimize a pairwise connectivity measure of an undirected graph via the removal of a subset of nodes (referred to as critical nodes) subject to a cardinality constraint. Potential applications include epidemic control, emergency response, vulnerability assessment, carbon emission monitoring, network security, and drug design. To solve the problem, we present a “reduce-solve-combine” memetic search approach that integrates a problem reduction mechanism into the popular population-based memetic algorithm framework. At each generation, a common pattern mined from two parent solutions is first used to reduce the given problem instance, then the reduced instance is solved by a component-based hybrid neighborhood search that effectively combines an articulation point impact strategy and a node weighting strategy, and finally an offspring solution is produced by combining the mined common pattern and the solution of the reduced instance. Extensive evaluations on 42 real-world and synthetic benchmark instances show the efficacy of the proposed method, which discovers nine new upper bounds and significantly outperforms the current state-of-the-art algorithms. Investigation of key algorithmic modules additionally discloses the importance of the proposed ideas and strategies. Finally, we demonstrate the generality of the proposed method via its adaptation to solve the node-weighted critical node problem. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72371157, 61903144, 72031007]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0130 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0130 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

A bottleneck-minimized colored traveling salesman problem is an important variant of colored traveling salesman problems. It is useful in handling the planning problems with partially overlapped workspace such as the scheduling transportation resources for timely delivery of goods. In this work, we propose an efficient bi-trajectory hybrid search method for it. The proposed method integrates a route-based crossover operator to generate promising offspring solutions, a multi-neighborhood simulated annealing to perform local optimization, and a stagnation-detect-escape mechanism to help the search escape from local optima. We also propose a bidirectional adjacency solution representation method to encode a solution, which extends the traditional adjacency representation method by additionally employing an array to represent its reverse counterpart. Extensive evaluations on two sets of 58 widely used benchmark instances demonstrate that the proposed method significantly outperforms state-of-the-art algorithms. Investigations on key algorithm modules are performed to confirm the novelty and effectiveness of the proposed ideas and strategies. Finally, we verify the generalization of the proposed method via its use to solve a colored traveling salesman problem with its aim to balance workload among salesmen. Note to Practitioners—This work is motivated by the problems of scheduling transportation resources for timely delivery of goods. It proposes an effective bi-trajectory hybrid search to tackle bottleneck-minimized colored traveling salesman problem. The proposed approach performs bi-trajectory hybrid evolutionary search by maintaining only two individuals during the whole search process. Extensive numerical experiments and comparisons show that our proposed algorithm significantly outperforms state-of-the-art algorithms and can help decision-makers in designing best-routing solutions.

Thek-vertex cut (k-VC) problem belongs to the family of the critical node detection problems, which aims to find a minimum subset of vertices whose removal decomposes a graph into at leastkconnected components. It is an important NP-hard problem with various real-world applications, e.g., vulnerability assessment, carbon emissions tracking, epidemic control, drug design, emergency response, network security, and social network analysis. In this article, we propose a fast local search (FLS) approach to solve it. It integrates a two-stage vertex exchange strategy based on neighborhood decomposition and cut vertex, and iteratively executes operations of addition and removal during the search. Extensive experiments on both intersection graphs of linear systems and coloring/DIMACS graphs are conducted to evaluate its performance. Empirical results show that it significantly outperforms the state-of-the-art (SOTA) algorithms in terms of both solution quality and computation time in most of the instances. To evaluate its generalization ability, we simply extend it to solve the weighted version of thek-VC problem. FLS also demonstrates its excellent performance.

The capacitated electric vehicle routing problem (CEVRP) extends the traditional vehicle routing problem by simultaneously considering the service order of the customers and the recharging schedules of the vehicles. Due to its NP-hard nature, we decompose the original problem into two sub-problems: a capacitated vehicle routing problem (CVRP) and a fixed route vehicle charging problem (FRVCP). A highly effective threshold acceptance based multi-layer search (TAMLS) algorithm is proposed to quickly obtain high-quality solutions. TAMLS consists of three layers. An iterated thresholding search procedure and a thresholding selection procedure are employed to produce diversified CVRP solutions in the first layer and to screen out high quality ones in the second layer, respectively. In the third layer, a removal heuristic coupling with an enumeration method is adopted to solve FRVRP, which produces optimized charging schedules. Extensive computational results show that TAMLS outperforms the state-of-the-art algorithms in terms of both solution quality and computation time. In particular, it is able to obtain new best results for 11 out of 17 benchmark instances, and reach the best known results on the remaining 6 instances. Additional experimental analyses are performed to better understand the contributions of key algorithmic components.

Previous researches on multimedia fake news detection include a series of complex feature extraction and fusion networks to gather useful information from the news. However, how cross-modal consistency relates to the fidelity of news and how features from different modalities affect the decision-making are still open questions. This paper presents a novel scheme of Bootstrapping Multi-view Representations (BMR) for fake news detection. Given a multi-modal news, we extract representations respectively from the views of the text, the image pattern and the image semantics. Improved Multi-gate Mixture-of-Expert networks (iMMoE) are proposed for feature refinement and fusion. Representations from each view are separately used to coarsely predict the fidelity of the whole news, and the multimodal representations are able to predict the cross-modal consistency. With the prediction scores, we reweigh each view of the representations and bootstrap them for fake news detection. Extensive experiments conducted on typical fake news detection datasets prove that BMR outperforms state-of-the-art schemes.

Fake news detection (FND) has attracted much research interests in social forensics. Many existing approaches introduce tailored attention mechanisms to fuse unimodal features. However, they ignore the impact of cross-modal similarity between modalities. Meanwhile, the potential of pretrained multimodal feature learning models in FND has not been well exploited. This paper proposes an FND-CLIP framework, i.e., a multimodal Fake News Detection network based on Contrastive Language-Image Pretraining (CLIP). FND-CLIP extracts the deep representations together from news using two unimodal encoders and two pair-wise CLIP encoders. The CLIP-generated multimodal features are weighted by CLIP similarity of the two modalities. We also introduce a modality-wise attention module to aggregate the features. Extensive experiments are conducted and the results indicate that the proposed framework has a better capability in mining crucial features for fake news detection. The proposed FND-CLIP can achieve better performances than previous works on three typical fake news datasets.

The easy sharing of multimedia content on social media has caused a rapid dissemination of fake news, which threatens society’s stability and security. Therefore, fake news detection has garnered extensive research interest in the field of social forensics. Current methods primarily concentrate on the integration of textual and visual features but fail to effectively exploit multi-modal information at both fine-grained and coarse-grained levels. Furthermore, they suffer from an ambiguity problem due to a lack of correlation between modalities or a contradiction between the decisions made by each modality. To overcome these challenges, we present a Multi-grained Multi-modal Fusion Network (MMFN) for fake news detection. Inspired by the multi-grained process of human assessment of news authenticity, we respectively employ two Transformer-based pre-trained models to encode token-level features from text and images. The multi-modal module fuses fine-grained features, taking into account coarse-grained features encoded by the CLIP encoder. To address the ambiguity problem, we design uni-modal branches with similarity-based weighting to adaptively adjust the use of multi-modal features. Experimental results demonstrate that the proposed framework outperforms state-of-the-art methods on three prevalent datasets.

The$\alpha $-separator problem ($\alpha $-SP) consists of finding the minimum set of vertices whose removal separates the network into multiple different connected components with fewer than a limited number of vertices in each component, which belongs to the family of critical node detection problems. The$\alpha $-SP problem is an important NP-hard problem with various real-world applications. In this paper, we propose a frequent itemset-driven search (FIS) algorithm to solve$\alpha $-SP, which integrates the concept of frequent itemset into the well-known memetic search framework. Starting from a high-quality population built by population construction and population repair, FIS then iteratively employs a frequent itemset recombination operator (to generate promising offspring solution), a tabu-based simulated annealing (to find local optima), a population repair procedure, and a population management strategy (to guarantee healthy/diverse population). Extensive evaluations on 50 benchmark instances show that FIS significantly outperforms the state-of-the-art algorithms. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds. Finally, we experimentally analyze the importance of each key algorithmic component, and perform a case study on an air transportation network for understanding its network structure and identifying its influential airports.

Videos are prone to tampering attacks that alter the meaning and deceive the audience. Previous video forgery detection schemes find tiny clues to locate the tampered areas. However, attackers can successfully evade supervision by destroying such clues using video compression or blurring. This paper proposes a video watermarking network for tampering localization. We jointly train a 3D-UNet-based watermark embedding network and a decoder that predicts the tampering mask under simulated attacks. The perturbation made by watermark embedding is close to imperceptible. Considering that there is no off-the-shelf differentiable video codec simulator, we propose to mimic video compression by ensembling simulation results of other typical attacks, e.g., JPEG compression and blurring, as an approximation. Experimental results demonstrate that our method generates watermarked videos with good imperceptibility and robustly and accurately locates tampered areas within the attacked version.

A coloring traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem, where colors are used to differentiate salesmen’s the accessibility to individual cities to be visited. As a useful model for a variety of complex scheduling problems, CTSP is computationally challenging. In this paper, we propose a Multi-neighborhood Simulated Annealing-based Iterated Local Search (MSAILS) to solve it. Starting from an initial solution, it iterates through three sequential search procedures: a multi-neighborhood simulated annealing search to find a local optimum, a local search-enhanced edge assembly crossover to find nearby high-quality solutions around a local optimum, and a solution reconstruction procedure to move away from the current search region. Experimental results on two groups of 45 medium and large benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it is able to discover new upper bounds for 29 instances while matching 8 previous best-known upper bounds. Hence, this work greatly advances the field of CTSP.

We present frequent pattern-based search (FPBS) that combines data mining and optimization. FPBS is a general-purpose method that unifies data mining and optimization within the population-based search framework. The method emphasizes the relevance of a modular- and component-based approach, making it applicable to optimization problems by instantiating the underlying components. To illustrate its potential for solving difficult combinatorial optimization problems, we apply the method to the well-known and challenging quadratic assignment problem. We show the computational results and comparisons on the hardest QAPLIB benchmark instances. This work reinforces the recent trend toward closer cooperations between the optimization methods and machine learning or data mining techniques.

Population-based memetic algorithms have been successfully applied to solve many difficult combinatorial problems. Often, a population of fixed size is used in such algorithms to record some best solutions sampled during the search. However, given the particular features of the problem instance under consideration, a population of variable size would be more suitable to ensure the best search performance possible. In this work, we propose a variable population memetic search (VPMS), where a strategic population sizing mechanism is used to dynamically adjust the population size during the search process. Our VPMS approach starts its search from a small population of only two solutions to focus on exploitation and then adapts the population size according to the search status to continuously influence the balancing between exploitation and exploration. We illustrate an application of the VPMS approach to solve the challenging critical node problem (CNP). We show that the VPMS algorithm integrating a variable population, an effective local optimization procedure, and a backbone-based crossover operator performs very well compared to state-of-the-art CNP algorithms. The algorithm is able to discover new upper bounds for 12 instances out of the 42 popular benchmark instances while matching 23 previous best-known upper bounds.

Clinical Named Entity Recognition (CNER) aims to automatically identity clinical terminologies in Electronic Health Records (EHRs), which is a fundamental and crucial step for clinical research. To train a high-performance model for CNER, it usually requires a large number of EHRs with high-quality labels. However, labeling EHRs, especially Chinese EHRs, is time-consuming and expensive. One effective solution to this issue is active learning, where a model asks labelers to annotate data which is beneficial to model performance improvement. Conventional active learning assumes a single labeler that always replies noiseless answers to queried labels. However, in real settings, multiple labelers provide diverse quality of annotation with varied cost and labelers with low overall annotation quality can still assign correct labels for some specific instances. In this paper, we propose a Cost-Quality Adaptive Active Learning (CQAAL) approach for CNER in Chinese EHRs, which maintains a balance between the annotation quality, labeling cost and the informativeness of selected instances. Specifically, our proposed CQAAL method selects cost-effective instance-labeler pairs to achieve better annotation quality with lower cost in an adaptive manner. Computational results on the CCKS2017 dataset demonstrate the superiority and effectiveness of CQAAL.

Registering a wrong hospital department is common when patients use on-line registering systems. Currently, there are some systems in practice. However, patients are unable to choose the best department due to different names and authorities of hospitals. To help solve the problem, we build a symptom-disease-disciplinary knowledge graph to recommend appropriate departments for patients. We obtain real disease-disciplinary information based on the regional health platform electronic health records (EHRs). Besides, we synthesize the symptom-disease relationship between ICD codes and medical encyclopedia websites. To further help the system predict the diseases based on patients' complaints, we update the weights of diseases through patients' choices in multi-round conversations. Experimental results show that the accuracy of final prediction is up to 92%.

Clinical text structuring is a critical and fundamental task for clinical research. Traditional methods such as task-specific end-to-end models and pipeline models usually suffer from the lack of dataset and error propagation. In this paper, we present a question answering based clinical text structuring (QA-CTS) task to unify different specific CTS tasks and make dataset shareable. A novel model that aims to introduce domain-specific features (e.g., clinical named entity information) into pre-trained language model is also proposed for QA-CTS task. Experimental results on Chinese pathology reports collected from Ruijing Hospital demonstrate our presented QA-CTS task is very effective to improve the performance on specific tasks. Our proposed model also competes favorably with strong baseline models in specific tasks.

Entity and relation extraction is the necessary step in structuring medical text. However, the feature extraction ability of the bidirectional long short term memory network in the existing model does not achieve the best effect. At the same time, the language model has achieved excellent results in more and more natural language processing tasks. In this paper, we present a focused attention model for the joint entity and relation extraction task. Our model integrates well-known BERT language model into joint learning through dynamic range attention mechanism, thus improving the feature representation ability of shared parameter layer. Experimental results on coronary angiography texts collected from Shuguang Hospital show that the F1-scores of named entity recognition and relation classification tasks reach 96.89% and 88.51%, which outperform state-of-the-art methods by 1.65% and 1.22%, respectively.

Electronic health record is an important source for clinical researches and applications, and errors inevitably occur in the data, which lead to severe damages to both patients and hospital services. One of such errors is the mismatch between diagnose and prescription, which we address as “medication anomaly” in the paper, and clinicians used to manually identify and correct them. With the development of machine learning techniques, researchers are able to train specific model for the task, but the process still requires expert knowledge to construct proper features, and few semantic relations are considered. In this paper, we propose a simple, yet effective detection method that tackles the problem by detecting the semantic inconsistency between diagnoses and prescriptions. Unlike traditional outlier or anomaly detection, the scheme uses continuous bag of words to construct the semantic connection between specific central words and their surrounding context. The detection of medication anomaly is transformed into identifying the least possible central word based on given context. To help distinguish the anomaly from normal context, we also incorporate a ranking accumulation strategy. The experiments were conducted on two real hospital electronic medical records, and the topN accuracy of the proposed method increased by 3.91 to 10.91% and 0.68 to 2.13% on the datasets, respectively, which is highly competitive to other traditional machine learning-based approaches.

Clinical named entity recognition aims to identify and classify clinical terms such as diseases, symptoms, treatments, exams, and body parts in electronic health records, which is a fundamental and crucial task for clinical and translational research. In recent years, deep neural networks have achieved significant success in named entity recognition and many other natural language processing tasks. Most of these algorithms are trained end to end, and can automatically learn features from large scale labeled datasets. However, these data-driven methods typically lack the capability of processing rare or unseen entities. Previous statistical methods and feature engineering practice have demonstrated that human knowledge can provide valuable information for handling rare and unseen cases. In this paper, we propose a new model which combines data-driven deep learning approaches and knowledge-driven dictionary approaches. Specifically, we incorporate dictionaries into deep neural networks. In addition, two different architectures that extend the bi-directional long short-term memory neural network and five different feature representation schemes are also proposed to handle the task. Computational results on the CCKS-2017 Task 2 benchmark dataset show that the proposed method achieves the highly competitive performance compared with the state-of-the-art deep learning methods.

Critical node problems (CNPs) involve finding a set of critical nodes from a graph whose removal results in optimizing a predefined measure over the residual graph. As useful models for a variety of practical applications, these problems are computationally challenging. In this paper, we study the classic CNP and introduce an effective memetic algorithm for solving CNP. The proposed algorithm combines a double backbone-based crossover operator (to generate promising offspring solutions), a component-based neighborhood search procedure (to find high-quality local optima), and a rank-based pool updating strategy (to guarantee a healthy population). Extensive evaluations on 42 synthetic and real-world benchmark instances show that the proposed algorithm discovers 24 new upper bounds and matches 15 previous best-known bounds. We also demonstrate the relevance of our algorithm for effectively solving a variant of the classic CNP, called the cardinality-constrained CNP. Finally, we investigate the usefulness of each key algorithmic component.

As a usual model for a variety of practical applications, the maximum diversity problem (MDP) is computational challenging. In this paper, we present an opposition-based memetic algorithm (OBMA) for solving MDP, which integrates the concept of opposition-based learning (OBL) into the well-known memetic search framework. OBMA explores both candidate solutions and their opposite solutions during its initialization and evolution processes. Combined with a powerful local optimization procedure and a rank-based quality-and-distance pool updating strategy, OBMA establishes a suitable balance between exploration and exploitation of its search process. Computational results on 80 popular MDP benchmark instances show that the proposed algorithm matches the best-known solutions for most of instances, and finds improved best solutions (new lower bounds) for 22 instances. We provide experimental evidences to highlight the beneficial effect of OBL for solving MDP.

There are hundreds of lakes in central China. Because of the dense population and low yield, lots of floodplain was reclaimed as farmland in recent hundreds of years. But after experiencing the tremendous flood disaster in the middle reaches of Yangzte River in 1998, wetlands restoration policy was soon proposed by the central government and implemented by the provinces in middle Yangtze. Poyang Lake is the largest freshwater lake in China. It lies in Jiangxi Province and is one of the key areas of wetlands restoration in middle Yangzte. Landsat TM/ETM images from 1998 to 2004 were used to monitor the area of wetlands restoration and assess its achievements around Poyang Lake in this paper. The result of wetlands restoration can be divided into tivo types: complete restoration and semirestoration. The former type is returning farmland to lake completely, while the latter is Just let farmers move away from the floodplain, the farmland was returned into lake only in flood season and can also be reaped in non-flood seasons. It Is testified that only 20 percents of the whole restoration area were the complete restoration, and about 80 percents of the wetlands restoration were semi-restoration around Poyang Lake.