Neural solvers have demonstrated remarkable success in combinatorial optimization, often surpassing traditional heuristics in speed, solution quality, and generalization. However, their efficacy deteriorates significantly when confronted with complex constraints that cannot be effectively managed through simple masking mechanisms. To address this limitation, we introduce Universal Constrained Preference Optimization (UCPO), a novel plug-and-play framework that seamlessly integrates preference learning into existing neural solvers via a specially designed loss function, without requiring architectural modifications. UCPO embeds constraint satisfaction directly into a preference-based objective, eliminating the need for meticulous hyperparameter tuning. Leveraging a lightweight warm-start fine-tuning protocol, UCPO enables pre-trained models to consistently produce near-optimal, feasible solutions on challenging constraint-laden tasks, achieving exceptional performance with as little as 1% of the original training budget.

Recent decomposition-based neural multi-objective combinatorial optimization (MOCO) methods struggle to achieve desirable performance. Even equipped with complex learning techniques, they often suffer from significant optimality gaps in weight-specific subproblems. To address this challenge, we propose a neat weight embedding method to learn weight-specific representations, which captures weight-instance interaction for the subproblems and was overlooked by most current methods. We demonstrate the potentials of our method in two instantiations. First, we introduce a succinct addition model to learn weight-specific node embeddings, which surpassed most existing neural methods. Second, we design an enhanced conditional attention model to simultaneously learn the weight embedding and node embeddings, which yielded new state-of-the-art performance. Experimental results on classic MOCO problems verified the superiority of our method. Remarkably, our method also exhibits favorable generalization performance across problem sizes, even outperforming the neural method specialized for boosting size generalization.

Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based methods suffer from low sample efficiency due to sparse rewards and underused solutions. We propose Best-anchored and Objective-guided Preference Optimization (BOPO), a training paradigm that leverages solution preferences via objective values. It introduces: (1) a best-anchored preference pair construction for better explore and exploit solutions, and (2) an objective-guided pairwise loss function that adaptively scales gradients via objective differences, removing reliance on reward models or reference policies. Experiments on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods, reducing optimality gaps impressively with efficient inference. BOPO is architecture-agnostic, enabling seamless integration with existing NCO models, and establishes preference optimization as a principled framework for combinatorial optimization.

We consider the robust routing problem with uncertain travel times under the min-max regret criterion, which represents an extended and robust version of the classic traveling salesman problem (TSP) and vehicle routing problem (VRP). The general budget uncertainty set is employed to capture the uncertainty, which provides the capability to control the conservatism of obtained solutions and covers the commonly used interval uncertainty set as a special case. The goal is to obtain a robust solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. Given the significant advancements and broad applications of neural combinatorial optimization methods in recent years, we present our initial attempt to combine neural approaches for solving this problem. We propose a dual multi-head cross attention mechanism to extract problem features represented by the inputted uncertainty sets. To tackle the built-in maximization problem, we derive the regret value by invoking a pre-trained model, subsequently utilizing it as the reward during the model training. Our experimental results on the robust TSP and VRP demonstrate the efficacy of our neural combinatorial optimization method, showcasing its ability to efficiently handle the robust routing problem of various sizes within a shorter time compared with alternative heuristic approaches.

Pickup and Delivery Problem with Time Windows (PDPTW) is a prevalent research direction in modern logistics transportation. In this challenging problem, customers are divided into pickup nodes and delivery nodes, and vehicles must first serve each pickup node before proceeding to its corresponding delivery node. Moreover, the hard time window constraint presents an obstacle for the existing learning-to-construct methods. Hence, this paper proposes a novel learning-to-construct approach based on node-pair insertion to address the complex time window constraint. It involves predicting the insertion point for the next node pair within the current partial solution and ensuring constraint adherence. We enhance the context information for the decoder to produce better solutions. The experimental results verify that the proposed approach can construct high-quality solutions in a very short period of time.

Thanks to the highly-expressive generative capabilities exhibited by diffusion models, recent works have shown their promising performance in combinatorial optimization (CO) problems, where the complicated problems are converted into the corrupting and denoising of heatmaps. The characteristics of diffusion-based approaches result in special advantages for Multi-Objective CO (MOCO) problems, especially MultiObjective Traveling Salesman Problem (MOTSP) better aligned with that solving paradigm. In this paper, we improve and adapt the diffusion-based approaches to tackle MOTSP, which are trained to generate various Pareto optimal solutions according to the problem decomposition strategies. Experimental results demonstrate that although the proposed approach may lag behind with the most advanced neural methods at present, it outperforms several traditional heuristics with a single graph neural network, indicating its effectiveness and potentiality in addressing MOCO problems.

Large language models (LLMs) have recently attracted significant attention and permeated diverse fields and disciplines. This paper aims to investigate the efficacy of LLMs in efficiently tackling combinatorial optimization problems and integrating them with traditional heuristic algorithms. Firstly, we describe the fundamental concepts and developmental history of LLMs, outlining the basic LLM framework involving the instance prompt, solution prompt, and algorithm prompt. Subsequently, we introduce a novel LLM implemented simulated annealing (SA) approach that enhances the basic LLM method. In the experiments, we present the average iterations required, convergence speed, and overall solution quality of LLM-based approaches in addressing the Traveling Salesman Problem (TSP). The results demonstrate that the integration of LLM with SA can enhance TSP-solving capabilities. Our research endeavors to empower non-specialists to effectively address combinatorial optimization problems.

We explore the robust traveling salesman problem (RTSP) with interval uncertainty under the min-max regret criterion, which enhances the classic traveling salesman problem (TSP) by focusing on robustness. Our aim is to develop a conservative solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. To achieve this, we integrate neural models into heuristic approaches, capitalizing on recent advancements in neural techniques. Specifically, we incorporate a pre-trained neural model into the tabu search framework, using it to refine the evaluation function. This novel integration streamlines the solution improvement process. Our experimental results underscore the effectiveness of this approach, showing that it handles various scales of the robust traveling salesman problem more efficiently and in less time compared to traditional heuristic methods.

Abstract Recently, graph neural networks (GNNs) have attracted much attention in the field of machine learning due to their remarkable success in learning from graph‐structured data. However, implementing GNNs in practice faces a critical bottleneck from the high complexity of communication and computation, which arises from the frequent exchange of graphic data during model training, especially in limited communication scenarios. To address this issue, we propose a novel framework of federated graph neural networks, where multiple mobile users collaboratively train the global model of graph neural networks in a federated way. The utilization of federated learning into the training of graph neural networks can help reduce the communication overhead of the system and protect the data privacy of local users. In addition, the federated training can help reduce the system computational complexity significantly. We further introduce a greedy‐based user selection for the federated graph neural networks, where the wireless bandwidth is dynamically allocated among users to encourage more users to attend the federated training of neural networks. We perform the convergence analysis on the federated training of neural networks, in order to obtain some more insights on the impact of critical parameters on the system design. Finally, we perform the simulations on the coriolis ocean for reAnalysis (CORA) dataset and show the advantages of the proposed method in this paper.

Pedestrian trajectory prediction is an essential task in real-world applications, aimed at predicting plausible future trajectories based on limited observations. In this work, we rethink the standard evaluation metric of the pedestrian trajectory prediction task: Minimum-of-N Average Displacement Error (MoN-ADE). As for multi-modal prediction models that generate multiple trajectories for each pedestrian, this metric typically evaluates the model by only considering the one that is closest to the ground-truth trajectory. However, such an evaluation protocol cannot comprehensively evaluate the predictive ability of the model, and potentially encourage models to generate high-variance and dispersed trajectory distributions. This is quite impractical especially for many real-world scenes like autonomous driving that require precise and convergent trajectory predictions. To address these limitations, we design a novel metric towards comprehensive evaluation in pedestrian trajectory prediction, which moves beyond the traditional reliance on the closest prediction. Specifically, we replace the Minimum-of-N strategy with an insightful Random-Sampling-K strategy to calculate the expectations of the minimum ADE and formulate a novel metric: Area Under the Curve (AUC). Furthermore, motivated by the proposed metric, we introduce a novel objective function named K-Ensemble Loss, which guides the state-of-the-art models to optimize the whole prediction distribution and reduce the uncertainty caused by the high-variance predictions. Extensive experiments on three real-world datasets demonstrate that the proposed metric and objective function are provided with significant effectiveness and flexibility.

5G vehicular networks provide abundant multimedia services among mobile vehicles. However, due to the mobility of vehicles, large-scale mobile traffic poses a challenge to the core network load and transmission latency. It is difficult for existing solutions to guarantee the quality of service (QoS) of vehicular networks. Besides, the sensitivity of vehicle trajectories also brings privacy concerns in vehicular networks. To address these problems, we propose a privacy-preserving and trajectory clustering-based framework for cooperative caching optimization (PTCC) in vehicular networks, which includes two tasks. Specifically, in the first task, we first apply differential privacy technologies to add noise to vehicle trajectories. In addition, a data aggregation model is provided to make the trade-off between aggregation accuracy and privacy protection. In order to analyze similar behavioral vehicles, trajectory clustering is then achieved by utilizing machine learning algorithms. In the second task, we construct a cooperative caching objective function with the transmission latency. Afterwards, the multi-agent deep Q network (MADQN) is leveraged to obtain the goal of caching optimization, which can achieve low delay. Finally, extensive simulation results verify that our framework respectively improves the QoS up to$9.8\%$and$12.8\%$with different file numbers and caching capacities, compared with other state-of-the-art solutions.

Recently, neural heuristics based on deep reinforcement learning have exhibited promise in solving multi-objective combinatorial optimization problems (MOCOPs). However, they are still struggling to achieve high learning efficiency and solution quality. To tackle this issue, we propose an efficient meta neural heuristic (EMNH), in which a meta-model is first trained and then fine-tuned with a few steps to solve corresponding single-objective subproblems. Specifically, for the training process, a (partial) architecture-shared multi-task model is leveraged to achieve parallel learning for the meta-model, so as to speed up the training; meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems. Experimental results on the multi-objective traveling salesman problem (MOTSP), multi-objective capacitated vehicle routing problem (MOCVRP), and multi-objective knapsack problem (MOKP) show that, EMNH is able to outperform the state-of-the-art neural heuristics in terms of solution quality and learning efficiency, and yield competitive solutions to the strong traditional heuristics while consuming much shorter time.

Most of existing neural methods for multi-objective combinatorial optimization (MOCO) problems solely rely on decomposition, which often leads to repetitive solutions for the respective subproblems, thus a limited Pareto set. Beyond decomposition, we propose a novel neural heuristic with diversity enhancement (NHDE) to produce more Pareto solutions from two perspectives. On the one hand, to hinder duplicated solutions for different subproblems, we propose an indicator-enhanced deep reinforcement learning method to guide the model, and design a heterogeneous graph attention mechanism to capture the relations between the instance graph and the Pareto front graph. On the other hand, to excavate more solutions in the neighborhood of each subproblem, we present a multiple Pareto optima strategy to sample and preserve desirable solutions. Experimental results on classic MOCO problems show that our NHDE is able to generate a Pareto front with higher diversity, thereby achieving superior overall performance. Moreover, our NHDE is generic and can be applied to different neural methods for MOCO.

A traveling salesman problem (TSP) is a well-known NP-complete problem. Traditional TSP presumes that the locations of customers and the traveling time among customers are fixed and constant. In real-life cases, however, the traffic conditions and customer requests may change over time. To find the most economic route, the decisions can be made constantly upon the time-point when the salesman completes his service of each customer. This brings in a dynamic version of the traveling salesman problem (DTSP), which takes into account the information of real-time traffic and customer requests. DTSP can be extended to a dynamic pickup and delivery problem (DPDP). In this article, we ameliorate the attention model to make it possible to perceive environmental changes. A deep reinforcement learning algorithm is proposed to solve DTSP and DPDP instances with a size of up to 40 customers in 100 locations. Experiments show that our method can capture the dynamic changes and produce a highly satisfactory solution within a very short time. Compared with other baseline approaches, more than 5% improvements can be observed in many cases.

Deep reinforcement learning (DRL) has recently shown its success in tackling complex combinatorial optimization problems. When these problems are extended to multiobjective ones, it becomes difficult for the existing DRL approaches to flexibly and efficiently deal with multiple subproblems determined by the weight decomposition of objectives. This article proposes a concise meta-learning-based DRL approach. It first trains a meta-model by meta-learning. The meta-model is fine-tuned with a few update steps to derive submodels for the corresponding subproblems. The Pareto front is then built accordingly. Compared with other learning-based methods, our method can greatly shorten the training time of multiple submodels. Due to the rapid and excellent adaptability of the meta-model, more submodels can be derived so as to increase the quality and diversity of the found solutions. The computational experiments on multiobjective traveling salesman problems and multiobjective vehicle routing problems with time windows demonstrate the superiority of our method over most of the learning-based and iteration-based approaches.

Emotion cause analysis (ECA) aims to extract emotion clauses and find the corresponding cause of the emotion. Existing methods adopt fine-tuning paradigm to solve certain types of ECA tasks. These task-specific methods have a deficiency of universality. And the relations among multiple objectives in one task are not explicitly modeled. Moreover, the relative position information introduced in most existing methods may make the model suffer from dataset bias. To address the first two problems, this paper proposes a universal prompt tuning method to solve different ECA tasks in the unified framework. As for the third problem, this paper designs a directional constraint module and a sequential learning module to ease the bias. Considering the commonalities among different tasks, this paper proposes a cross-task training method to further explore the capability of the model. The experimental results show that our method achieves competitive performance on the ECA datasets.

Vehicle routing problem with time windows (VRPTW) is an important topic in modern delivery companies. Optimizing the vehicle routes not only reduces the transportation cost but also increases the customers' satisfaction. In literature, there are many studies focusing on symmetric vehicle routing problems. However, due to the transportation network and traffic conditions, the traveling distance and traveling time may be asymmetric in practical scenarios. In this paper, we formulate a practical VRPTW from the perspective of edges. With the edge-based formulation, a novel deep reinforcement learning model based on graph attention network is proposed. Two benchmark sets of practical VRPTW for training and testing are generated from the real-world data. The experimental results on the benchmark sets demonstrate that our method can outperform node-based and other well-known methods.

The job-shop scheduling problem (JSSP) is a classic combinatorial optimization problem in the areas of computer science and operations research. It is closely associated with many industrial scenarios. In today’s society, the demand for efficient and stable scheduling algorithms has significantly increased. More and more researchers have recently tried new methods to solve JSSP. In this paper, we effectively formulate the scheduling process of JSSP as a Semi-Markov Decision Process. We then propose a method of using hierarchical reinforcement learning with graph neural networks to solve JSSP. We also demonstrate that larger-sized instances require the support of a bigger number of sub-policies and different scheduling phases require using different sub-policies.

The multiobjective combinatorial optimization problems (MOCOPs) have a wide range of real-world applications. Designing an effective algorithm has an important and practical significance. Due to the huge search space and limited time, it is generally difficult to obtain the optimal solution of this kind of problem by traditional exact and heuristic algorithms. Recently, learning-based algorithms have achieved good results in solving MOCOPs, but the quality and diversity of found solutions can be further improved. In this paper, we propose a Weight-Specific-Decoder Attention Model (WSDAM) to better approximate the whole Pareto set. It embeds a weight-adaptive layer into the decoder to concentrate on the information of different weight vectors. During the model training, the weight vector is sampled from the Dirichlet distribution, which can further strengthen the learning of boundary solutions. We evaluate our method on two classic MOCOPs, i.e., the multiobjective traveling salesman problem (MOTSP) and multiobjective capacitated vehicle routing problem (MOCVRP). The experimental results show that our proposed method outperforms current state-of-the-art learning-based methods in both solution quality and generalization ability.

There are many combinatorial optimization problems derived from the classic traveling salesman problem (TSP). The quadratic traveling salesman problem (QTSP) is one of them. It needs to consider the relationship between three successive nodes rather than two successive nodes. In literature, there are exact methods based on integer programming and approximate methods based on heuristics for solving QTSP. In this paper, we try to adopt deep reinforcement learning to tackle QTSP. We consider two classic QTSPs studied in the previous literature, namely the angular-metric TSP and the angular-distance-metric TSP. Both of them consider the turning angle for each node, and the angular-distance-metric TSP further considers the total traveling distance in the original TSP. The experimental results show that our method is superior to some typical heuristic methods in terms of solution quality, and better than the exact methods in terms of time.

Motivated by some practical applications in urban services such as water sparkling, we study a split-delivery capacitated arc-routing problem with time windows (SDCARPTW). It is a variant of arc-routing problem and is defined on an undirected graph where the demands on the arcs are splitable, and time window and capacity constraints must be satisfied. We propose a mathematical formulation for SDCARPTW and derive some nice properties of the split-delivery structure, which can help to well represent a solution of SDCARPTW. The dynamic programming, neighborhood search and perturbation process are combined to develop a tabu search algorithm. Through computational studies on CARPTW benchmark datasets, we validate the effectiveness and efficiency of our proposed algorithm. New datasets for SDCARPTW are further proposed and the impact of the split-delivery option is analyzed.

Convergence, diversity and feasibility are three important issues when solving constrained multiobjective optimization problems (CMOPs). To deal with the balance among convergence, diversity and feasibility well, this article proposes a cooperative multiobjective evolutionary algorithm with propulsive population (CMOEA-PP) for solving CMOPs. CMOEA-PP has two populations, including propulsive population and normal population, and these two populations work cooperatively. Specifically, propulsive population focuses on convergence. Normal population gives priority to feasibility and is obligated to maintain diversity. To cross through the infeasible region and reach the Pareto front (PF), propulsive population does not consider constraints in the early stage and only considers constraints in the later stage. To further accelerate the speed of convergence, propulsive population only searches for corner solutions and center solutions, while normal population searches for the whole PF. As a result, propulsive population can cross through the infeasible region because of the lack of attention to feasibility. In addition, propulsive population also can guide and accelerate the convergence of the evolutionary process. Comprehensive experiment results on several sets of benchmark problems demonstrate that CMOEA-PP is better than existing state-of-the-art competitors.

Learning-based heuristics for solving combinatorial optimization problems has recently attracted much academic attention. While most of the existing works only consider the single objective problem with simple constraints, many real-world problems have the multiobjective perspective and contain a rich set of constraints. This paper proposes a multiobjective deep reinforcement learning with evolutionary learning algorithm for a typical complex problem called the multiobjective vehicle routing problem with time windows (MO-VRPTW). In the proposed algorithm, the decomposition strategy is applied to generate subproblems for a set of attention models. The comprehensive context information is introduced to further enhance the attention models. The evolutionary learning is also employed to fine-tune the parameters of the models. The experimental results on MO-VRPTW instances demonstrate the superiority of the proposed algorithm over other learning-based and iterative-based approaches.

Traveling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem. Recently, many researchers have used deep reinforcement learning to solve it. However, traffic factors are rarely considered in their works, in which the traveling time between customer locations is assumed to be constant over the planning horizon. For many practical scenarios, the traffic conditions between customer locations may change over time due to the impact of traffic patterns. Thus, this paper considers a Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW), where the time dependency is obtained by fitting the collected traffic data into real-time traffic function with the interpolation method. We propose a deep reinforcement learning framework to solve TDTSPTW. Extensive experiments on TDTSPTW instances indicate that the proposed method can capture the real-time traffic changes and yield high-quality solutions within a very short time, compared with other typical baseline algorithms.

This paper presents an arc-routing problem with time-dependent penalty cost (ARPTPC), which arises from a practical application in garbage collection service. ARPTPC considers the minimization of service cost, traveling cost and penalty cost. While the first two parts are known as the traditional objectives of arc-routing problems, the third part is determined by the parking pattern and service period on each arc. We formulate the problem by using a mixed integer linear model. To solve it, we design a dynamic programming to determine the optimal service beginning time on each edge when a routing sequence is given. We then propose a problem-specific intelligent heuristic search approach involving six neighborhood operators, a priority maintenance mechanism and a perturbation process. Through numerical experiments, we demonstrate that the proposed approach is able to produce satisfactory solutions of ARPTPC. Additional experiments are also carried out to analyze the effects of operators and parameters on solution quality.

This paper introduces a multiobjective fleet size and mix location-routing problem with time windows and designs a set of real-world benchmark instances. Then, two versions of multiobjective multiple neighborhood search algorithms based on decomposition and vector angle are developed for solving the problem. In the proposed algorithms, three different kinds of neighborhood search operators, including general local search, objective-specific local search, and large neighborhood search, are carefully designed and combined in a synergistic manner. The experimental results show the effectiveness of the proposed algorithms. Relationships between different objectives in this multiobjective problem are also discussed.

In this paper, we propose an enhanced branch-and-bound (B&B) framework for a class of sequencing problems, which aim to find a permutation of all involved elements to minimize a given objective function. We require that the sequencing problems satisfy three conditions: 1) incrementally computable; 2) monotonic; and 3) overlapping subproblems. Our enhanced B&B framework is built on the classical B&B process by introducing two techniques, i.e., dominance rules and caching search states. Following the enhanced B&B framework, we conduct empirical studies on three typical and challenging sequencing problems, i.e., quadratic traveling salesman problem, traveling repairman problem, and talent scheduling problem. The computational results demonstrate the effectiveness of our enhanced B&B framework when compared to classical B&B and some exact approaches, such as dynamic programming and constraint programming. Additional experiments are carried out to analyze different configurations of the algorithm.

An airline crew rostering problem (ACRP) is one of the most important problems in an airline planning process. It aims at determining an optimal assignment of pairings, which refer to sequences of flights starting from and ending at the same crew base, to aircrew to form roster lines. In practice, ACRP is subject to various types of constraints. We present a constraint-implicit mathematical model taking into account the basic, horizontal, and vertical constraints. In order to solve a kind of ACRP, we propose a construction-based variable neighborhood search (VNS) framework that can build rosters effectively. Three construction methods, i.e., crew-by-crew, pairing-by-pairing, and orthogonal constructions, are introduced. To evaluate our approaches, we conduct extensive experiments on two scenarios (intense and light workload) of instances originated from a Chinese airline company and make comparisons among different VNS approaches. The computational results show that the proposed approaches are capable of producing high-quality solutions in both scenarios.

An importer in Hong Kong employs vehicles, all from external transport companies, to deliver products to its customers geographically scattered in different locations. The delivery plan needs to simultaneously minimize the total traveling cost and balance the profits among all transport companies. This transportation practice engenders a new variant of vehicle routing problems, called the vehicle routing problem with outsourcing and profit balancing (VRPOPB). The profits are balanced by maximizing the minimum unit profit of all transport companies, which can effectively avoid the occurrence of distorted solutions. We develop two multi-objective local search (MOLS) algorithms for the problem, where the second one enhances the first one by incorporating several additional techniques. To evaluate our algorithms, we conduct extensive experiments on 57 generated instances and a real case obtained from a food importer in Hong Kong. The computational results clearly demonstrate that our enhanced MOLS algorithm is able to achieve satisfactory solutions.

Periodic vehicle routing problem with time windows (PVRPTWs) is an important combinatorial optimization problem that can be applied in different fields. It is essentially a multiobjective optimization problem due to the problem nature. In this paper, a typical multiobjective PVRPTW with five objectives is first defined and new nonsymmetric real-world multiobjective PVRPTW instances are generated. Then, a hybrid multiobjective memetic algorithm is proposed for solving multiobjective PVRPTW. In the proposed algorithm, a two-phase strategy is devised to improve the comprehensive performance in terms of the convergence and diversity. In this strategy, several extreme solutions near an approximate Pareto front (PF) are identified at Phase I, and then the approximate PF is extended at Phase II. The proposed algorithm is extensively tested on both real-world instances and traditional instances. Experiment results show that the proposed algorithm outperforms two representative competitor algorithms on most of the instances. The effectiveness of the two-phase strategy is also confirmed.

It is generally accepted that the essential goal of many-objective optimization is the balance between convergence and diversity. For constrained many-objective optimization problems (CMaOPs), the feasibility of solutions should be considered as well. Then the real challenge of constrained many-objective optimization can be generalized to the balance among convergence, diversity, and feasibility. In this paper, a tri-goal evolution framework is proposed for CMaOPs. The proposed framework carefully designs two indicators for convergence and diversity, respectively, and converts the constraints into the third indicator for feasibility. Since the essential goal of constrained many-objective optimization is to balance convergence, diversity, and feasibility, the philosophy of the proposed framework matches the essential goal of constrained many-objective optimization well. Thus, it is natural to use the proposed framework to deal with CMaOPs. Further, the proposed framework is conceptually simple and easy to instantiate for constrained many-objective optimization. A variety of balance schemes and ranking methods can be used to achieve the balance among convergence, diversity and feasibility. Three typical instantiations of the proposed framework are then designed. Experimental results on a constrained many-objective optimization test suite show that the proposed framework is highly competitive with existing state-of-the-art constrained many-objective evolutionary algorithms for CMaOPs.

Mobile sequential recommendation was originally designed to find a promising route for a single taxicab. Directly applying it for multiple taxicabs may cause an excessive overlap of recommended routes. The multi-taxicab recommendation problem is challenging and has been less studied. In this paper, we first formalize a collective mobile sequential recommendation problem based on a classic mathematical model, which characterizes time-varying influence among competing taxicabs. Next, we propose a new evaluation metric for a collection of taxicab routes aimed to minimize the sum of potential travel time. We then develop an efficient algorithm to calculate the metric and design a greedy recommendation method to approximate the solution. Finally, numerical experiments show the superiority of our methods. In trace-driven simulation, the set of routes recommended by our method significantly outperforms those obtained by conventional methods.

In subway systems, kinetic energy can be converted into electrical one by using regenerative braking systems. If regenerative energy (RE) is fully used, the energy demands from power grid can be dramatically reduced. Since energy storage systems usually have a high cost, they are not considered in this work. Thus, RE has to be immediately utilized by accelerating trains; otherwise, it is wasted into heat via resistors. Timetable optimization methods are often used to coordinate accelerating and braking trains at a station, such that RE can be optimally used by the former. To improve RE utilization (REU) in a subway line, we propose a timetable optimization problem and establish its mathematical model. Many realistic constraints with the decision variables, i.e., headway time and dwell time, are considered. Then we design an improved artificial bee colony (IABC) algorithm to solve the problem. Several numerical experiments are conducted based on the actual data from a subway line in Beijing, China. The correctness of the mathematical model and effectiveness of IABC are shown by comparing it with commercial software CPLEX and a genetic algorithm, respectively. The impact of the decision variables on REU is analyzed, which helps to improve the timetable currently used in this subway line. We also test the robustness of the optimized timetable when certain disturbance takes place.

The quay crane scheduling problem (QCSP) is one of the most important problems for the operations at container ports. The QCSP aims to decide a QC schedule for loading and unloading containers so as to minimize the vessel turnaround time. The QCSP is subject to various kinds of constraints, e.g., task precedence constraints and QC noninterference constraints. This paper extends the QCSP by taking into consideration the stability constraints, which are crucial for the safety reason but often omitted in the existing literature. We provide a mathematical model for the QCSP with stability constraints (QCSPSCs). A bicriteria evolutionary algorithm is proposed to solve the QCSPSC. The algorithm consists of a sliding-window heuristic to fix the schedule, which violates the stability constraints. Extensive experiments are conducted to demonstrate the effectiveness of the algorithm. The computational results of the traditional QCSP and the QCSPSC are also compared and analyzed.

The ship stowage planning problem (SSPP) is a very complex and challenging problem in the logistics industries because it affects the benefits of both shipping lines and port terminals. In this paper, we investigate a multiobjective SSPP, which aims to optimize the ship stability and the number of rehandles simultaneously. We use metacentric height, list value, and trim value to measure the ship stability. Meanwhile, the number of rehandles is the sum of rehandles by yard cranes and quay cranes and all necessary rehandles at future ports. To solve this problem, a variant of the nondominated sorting genetic algorithm III (NSGA-III) combined with a local search component is proposed. The algorithm can produce a set of nondominated solutions. Decision makers can then choose the most promising solution for practical implementation based on their experience and preferences. Extensive experiments are carried out on two groups of instances. The computational results demonstrate the effectiveness of the proposed algorithm compared to the NSGA-II and random weighted genetic algorithms, especially when it is applied in solving the six-objective SSPP.

The split-delivery vehicle routing problem (SDVRP) is a natural extension of the classical vehicle routing problem (VRP) that allows the same customer to be served by more than one vehicle. This problem is a very challenging combinatorial optimization problem and has attracted much academic attention. To solve it, most of the literature articles adopted heuristic approaches in which the solution is represented by a set of delivery patterns, and the search operators were derived from the traditional VRP operators. Differently, our approach employs the combination of a set of routes and a forest to represent the solution. Several forest-based operators are accordingly introduced. We integrate the new operators into a simple tabu search framework and then demonstrate the efficiency of our approach by conducting experiments on existing benchmark instances.

In today's global free market, third-party logistics providers (3PLs) are becoming increasingly important. This paper studies a problem faced by a 3PL operating a warehouse in Shanghai, China, under contract with a major company for children's clothing based in the United States. The problem involves the allocation of textile parcel shipments at the warehouse to shipping routes with different destination ports, where the shipments are destined for different retail stores. The shipments must be loaded into containers of varying sizes and costs, and the objective is to find an allocation that minimizes the total container transportation and parcel delivery costs. We formulate the problem into an integer linear programming model, and also propose a genetic algorithm approach to solve the problem practically. A demonstration of a good solution to this problem was a decisive factor in the awarding of the contract to the 3PL in question.