Symbiotic organisms search and two solution representations for solving the capacitated vehicle routing problem

This paper presents the symbiotic organisms search (SOS) heuristic for solving the capacitated vehicle routing problem (CVRP), which is a well-known discrete optimization problem. The objective of CVRP is to decide the routes for a set of vehicles to serve a set of demand points while minimizing the total routing cost. SOS is a simple and powerful metaheuristic that simulates the symbiotic interaction strategies adopted by an organism for surviving in an ecosystem. As SOS is originally developed for solving continuous optimization problems, we therefore apply two solution representations, SR-1 and SR-2, to transform SOS into an applicable solution approach for CVRP and then apply a local search strategy to improve the solution quality of SOS. The original SOS uses three interaction strategies, mutualism, commensalism, and parasitism, to improve a candidate solution. In this improved version, we propose two new interaction strategies, namely competition and amensalism. We develop six versions of SOS for solving CVRP. The first version, SOS_Canonical, utilizes a commonly used continuous to discrete solution representation transformation procedure. The second version is an improvement of canonical SOS with a local search strategy, denoted as SOS_Basic. The third and fourth versions use SR-1 and SR-2 with a local search strategy, denoted as SOS_SR-1 and SOS_SR-2. The fifth and sixth versions, denoted as ISOS_SR-1 and ISOS_SR-2, improve the implementation of SOS_SR-1 and SOS_SR-2 by adding the newly proposed competition and amensalism interaction strategies. The performances of SOS_Canonical, SOS_Basic, SOS_SR-1, and SOS_SR-2 are evaluated on two sets of benchmark problems. First, the results of the four versions of SOS are compared, showing that the preferable result was obtained from SOS_SR-1 and SOS_SR-2. The performances of SOS_SR-1, SOS_SR-2, ISOS_SR-1, and ISOS_SR-2 are then compared, presenting that ISOS_SR-1 and ISOS_SR-2 offer a better performance. Next, the ISOS_SR-1 and ISOS_SR-2 results are compared to the best-known solutions. The results show that ISOS_SR-1 and ISOS_SR-2 produce good VRP solutions under a reasonable computational time, indicating that each of them is a good alternative algorithm for solving the capacitated vehicle routing problem.     

A multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem

The aim of this study is to solve the newspaper delivery optimization problem for a media delivery company in Turkey by reducing the total cost of carriers. The problem is modelled as an open vehicle routing problem (OVRP), which is a variant of the vehicle routing problem. A variable neighbourhood search-based algorithm is proposed to solve a real-world OVRP. The proposed algorithm is tested with varieties of small and large-scale benchmark suites and a very large-scale real-world problem instance. The results of the proposed algorithm provide either the best known solution or a competitive solution for each of the benchmark instances. The algorithm also improves the real-world company’s solutions by more than 10%.     

An iterated local search heuristic for the split delivery vehicle routing problem

This paper concerns the Split Delivery Vehicle Routing Problem (SDVRP). This problem is a relaxation of the Capacitated Vehicle Routing Problem (CVRP) since the customers׳ demands are allowed to be split. We deal with the cases where the fleet is unlimited (SDVRP-UF) and limited (SDVRP-LF). In order to solve them, we implemented a multi-start Iterated Local Search (ILS) based heuristic that includes a novel perturbation mechanism. Extensive computational experiments were carried out on benchmark instances available in the literature. The results obtained are highly competitive, more precisely, 55 best known solutions were equaled and new improved solutions were found for 243 out of 324 instances, with an average and maximum improvement of 1.15% and 2.81%, respectively.     

A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints

The capacitated vehicle routing problem with three-dimensional loading constraints combines capacitated vehicle routing and three-dimensional loading with additional packing constraints concerning, for example, unloading operations. An efficient hybrid algorithm including a tabu search algorithm for routing and a tree search algorithm for loading is introduced. Computational results are presented for all publicly available test instances. Most of the best solutions previously reported in literature have been improved while the computational effort is drastically reduced compared to other methods.     

A two-phase metaheuristic for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem, which aims to minimize the total arrival time at customers, is a relatively new variant of vehicle routing problem. It can be used to model many real-world applications, e.g., the important application arisen from the humanitarian aid after a natural disaster. In this paper, an approach, called two-phase metaheuristic, is proposed to deal with this problem. This algorithm starts from a solution. At each iteration, two interdependent phases use different perturbation and local search operators for solution improvement. The effectiveness of the proposed algorithm is empirically investigated. The comparison results show that the proposed algorithm is promising. Moreover, for nine benchmark instances, the two-phase metaheuristic can find better solutions than those reported in the previous literature.     

Dynamic vehicle routing using genetic algorithms

Many difficult combinatorial optimization problems have been modeled as static problems. However, in practice, many problems are dynamic and changing, while some decisions have to be made before all the design data are known. For example, in the Dynamic Vehicle Routing Problem (DVRP), new customer orders appear over time, and new routes must be reconfigured while executing the current solution. Montemanni et al. [1] considered a DVRP as an extension to the standard vehicle routing problem (VRP) by decomposing a DVRP as a sequence of static VRPs, and then solving them with an ant colony system (ACS) algorithm. This paper presents a genetic algorithm (GA) methodology for providing solutions for the DVRP model employed in [1]. The effectiveness of the proposed GA is evaluated using a set of benchmarks found in the literature. Compared with a tabu search approach implemented herein and the aforementioned ACS, the proposed GA methodology performs better in minimizing travel costs. Franklin T. Hanshar is currently a M.Sc. student in the Department of Computing and Information Science at the University of Guelph, Ontario, Canada. He received a B.Sc. degree in Computer Science from Brock University in 2005. His research interests include uncertain reasoning, optimization and evolutionary computation. Beatrice Ombuki-Berman is currently an Associate Professor in the Department of Computer Science at Brock University, Ontario, Canada. She obtained a PhD and ME in Information Engineering from University of The Ryukyus, Okinawa, Japan in 2001 and 1998, respectively. She received a B.Sc. in Mathematics and Computer Science from Jomo Kenyatta University, Nairobi, Kenya. Her primary research interest is evolutionary computation and applied optimization. Other research interests include neural networks, machine learning and ant colony optimization.     

A cooperative parallel metaheuristic for the capacitated vehicle routing problem

This paper introduces a cooperative parallel metaheuristic for the capacitated vehicle routing problem. The proposed metaheuristic consists of multiple parallel tabu search threads that cooperate by asynchronously exchanging best-found solutions through a common solution pool. The solutions sent to the pool are clustered according to their similarities. The search history information identified from the solution clusters is applied to guide the intensification or diversification of the tabu search threads. Computational experiments on two sets of large-scale benchmark instance sets from the literature demonstrate that the suggested metaheuristic is highly competitive, providing new best solutions to ten of those well-studied instances.     

基于禁忌搜索算法的线路规划方案求解

针对物流部门中出现的时间窗和车辆限制的开放性车辆线路问题（open vehicle routing problem with time window and vehicle limits,m-OVRPTW）,提出基于禁忌搜索算法的线路规划方案。对问题进行数学建模;通过设计4种邻域变化规则、设定多个禁忌长度来改进局部搜索,快速得到高质量近似解,解决m-OVRPTW问题;通过反复选取车辆数量,解决OVRPTW问题。用56组Solomon基准测试数据（VRPTW benchmark problem）进行测试,测试结果表明,将禁忌搜索算法应用在开放性车辆线路问题中取得了较好成果,其在最小车辆数量、最小车辆行程、平均车辆总行程等方面的表现都优于其它算法。     

The open capacitated arc routing problem

The Open Capacitated Arc Routing Problem (OCARP) is a NP-hard combinatorial optimization problem where, given an undirected graph, the objective is to find a minimum cost set of tours that services a subset of edges with positive demand under capacity constraints. This problem is related to the Capacitated Arc Routing Problem (CARP) but differs from it since OCARP does not consider a depot, and tours are not constrained to form cycles. Applications to OCARP from literature are discussed. A new integer linear programming formulation is given, followed by some properties of the problem. A reactive path-scanning heuristic, guided by a cost-demand edge-selection and ellipse rules, is proposed and compared with other successful CARP path-scanning heuristics from literature. Computational tests were conducted using a set of 411 instances, divided into three classes according to the tightness of the number of vehicles available; results reveal the first lower and upper bounds, allowing to prove optimality for 133 instances.     

基于暂态混沌神经网络的多车调度混合优化算法

探讨车辆调度问题的解决方法．提出一种用于求解带容量约束的多车调度问题（CVRP）的混合优化算法．该算法分为路线划分、构造初始解和改进解3个阶段：第1阶段用模糊C均值聚类算法将所有客户按车容量要求装车;第2阶段用暂态混沌神经网络方法对每条路线排序;第3阶段用禁忌搜索法改进得到的解．最后采用标准问题进行仿真计算,通过与其他算法的比较,说明该算法是求解CVRP问题可行且高效的方法．     

An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size

The generalized vehicle routing problem (GVRP) involves finding a minimum-length set of vehicle routes passing through a set of clusters, where each cluster contains a number of vertices, such that the tour includes exactly one vertex from each cluster and satisfies capacity constraints. We consider a version of the GVRP where the number of vehicles is a decision variable. This paper introduces a new mathematical formulation based on a two-commodity flow model. We solve the problem using a branch-and-cut algorithm and a metaheuristic that is a hybrid of the greedy randomized adaptive search procedure (GRASP) and the evolutionary local search (ELS) proposed in [18]. We perform computational experiments on instances from the literature to demonstrate the performance of our algorithms.     

A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP).     

Exact and metaheuristic algorithms for the vehicle routing problem with a factory-in-a-box in multi-objective settings

Emergencies, such as pandemics (e.g., COVID-19), warrant urgent production and distribution of goods under disrupted supply chain conditions. An innovative logistics solution to meet the urgent demand during emergencies could be the factory-in-a-box manufacturing concept. The factory-in-a-box manufacturing concept deploys vehicles to transport containers that are used to install production modules (i.e., factories). The vehicles travel to customer locations and perform on-site production. Factory-in-a-box supply chain optimization is associated with a wide array of decisions. This study focuses on selection of vehicles for factory-in-a-box manufacturing and decisions regarding the optimal routes within the supply chain consisting of a depot, suppliers, manufacturers, and customers. Moreover, in order to contrast the options of factory-in-a-box manufacturing with those of conventional manufacturing, the location of the final production is determined for each customer (i.e., factory-in-a-box manufacturing with production at the customer location or conventional manufacturing with production at the manufacturer locations). A novel multi-objective optimization model is presented for the vehicle routing problem with a factory-in-a-box that aims to minimize the total cost associated with traversing the edges of the network and the total cost associated with visiting the nodes of the network. A customized multi-objective hybrid metaheuristic solution algorithm that directly considers problem-specific properties is designed as a solution approach. A case study is performed for a vaccination project involving factory-in-a-box manufacturing along with conventional manufacturing. The case study reveals that the developed solution method outperforms the ε-constraint method, which is a classical exact optimization method for multi-objective optimization problems, and several well-known metaheuristics.     

An improved hybrid firefly algorithm for capacitated vehicle routing problem

Firefly algorithm (FA) is a new meta-heuristic which is successfully applied to solve several optimization problems. However, it suffers from a drawback of easily getting stuck at local optima. This paper proposes a new hybrid FA, called CVRP-FA, to solve capacitated vehicle routing problem. In CVRP-FA, FA is integrated with two types of local search and genetic operators to enhance the solution’s quality and accelerate the convergence. The experiments are conducted over 82 benchmark instances. The results demonstrate that CVRP-FA has fast convergence rate and high computational accuracy. It significantly outperforms the other state-of-the-art FA variants in majority of the tested instances.     

A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service

The vehicle routing problem with simultaneous pick-up and delivery (VRP_SPD) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous pick-up and delivery service. Deliveries are supplied from a single depot at the beginning of the vehicle's service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle's load in any given route is a mix of pick-up and delivery loads.     

Site dependent vehicle routing problem with soft time window: Modeling and solution approach

This paper presents two meta-heuristic algorithms, an ant colony system with local searches and a tabu search algorithm, for Site-Dependent Vehicle Routing Problem with Soft Time Window (SDVRPSTW). In the SDVRPSTW a fleet of vehicles must deliver goods to their allowable set of customers, preferably in their time windows while the capacity constraints of the vehicles must be respected. Based on our best knowledge, this problem which challenges the distribution task of public services and private organizations in an urban context with heavy traffic has not yet been considered in practical aspects, especially where the vehicles entrance to some areas needs traffic license. Hence, in addition to present an Integer Linear Programming (ILP) model, we present the two mentioned algorithms to handle the problem in large scale instances. Furthermore, the algorithms efficiency and their optimality are analyzed by experimental results both in small and large dimensions.     

A matheuristic for the MinMax capacitated open vehicle routing problem

In this paper, the MinMax‐COVRP (where COVRP is capacitated open vehicle routing problem) is considered as a variation of the COVRP where the objective is to minimize the duration of the longest route. For the purpose of producing high‐quality solutions, elements from the fields of mathematical programming and metaheuristics are combined, resulting in a matheuristic for solving the MinMax‐COVRP. The matheuristic benefits from the diversification produced by a metaheuristic and the intensification from mixed‐integer linear programming (MILP). The initial solution provided by a multistart heuristic is used to seed and accelerate the MILP in which a local branching framework and the separation of k‐path inequalities are suitably combined. Computational experience shows promising results not only improving the initial solution provided by the multistart algorithm, but also ensuring optimality for most of the small‐ and medium‐sized instances.     

A metaheuristic for a teaching assistant assignment-routing problem

The Flemish Ministry of Education promotes the integrated education of disabled children by providing educational opportunities in common schools. In the current system, disabled children receive ambulant help from a teaching assistant (TA) employed at an institute for extra-ordinary education. The compensation that the TAs receive for driving to visit the pupils is a major cost factor for the institute that provides the assistance. Therefore, the institute's management desires a schedule that minimizes the accumulated distance traveled by all TAs combined. We call this optimization problem the teaching assistants assignment-routing problem (TAARP). It involves three decisions that have to be taken simultaneously: (1) pupils have to be assigned to TAs; (2) pupils assigned to a given TA have to be spread over the TA's different working days; and (3) the order in which to visit the pupils on each day has to be determined. We propose a solution strategy based on an auction algorithm and a variable neighborhood search heuristic which has an excellent performance when applied to both simulated and real instances. The total distance traveled in the solution obtained for the institute's data set improves the current solution by about 22% which represents a saving of approximately 9% on the annual budget of the institute for integrated education.     

A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem

In the heterogeneous fixed fleet vehicle routing problem there are different types of vehicles and a given number of vehicles of each type. The resolution of this problem consists of assigning the customers to the existing vehicles and, in relation to each vehicle, defining the order of visiting each customer for the delivery or collection of goods. The objective is to minimize the total costs, satisfying customers’ requirements and visiting each customer exactly once. In this paper a tabu search algorithm is proposed and tested on several benchmark problems. The computational experiments show that the proposed algorithm produces high quality solutions within an acceptable computation time. Four new best solutions are reported for a set of test problems used in the literature.     

An improved LNS algorithm for real-time vehicle routing problem with time windows

This paper studies the dynamic vehicle routing problem with hard time windows (DVRPTW). The main study course of this problem was briefly reviewed. The solving strategy and algorithm of the problem are put forward. First of all, DVRPTW problem is decomposed into a series of static VRPTW. When and how to decompose the DVRP is the issue, that must be addressed. An event-trigger mechanism has been proposed and used to decompose the DVRPTW into a series of system delay-snapshots. The trigger event to be adopted is a new request arrival during the stable operation. And each snapshot is regarded as a static VRPTW. Whether each static VRPTW can quickly and efficiently be solved within a given time or a shorter time, i.e. the solving time is another issue for the DVRPTW. In the solving process, how to merge the latest requirement to the current solution is the third issue that must be solved. An improved large neighborhood search (LNS) algorithm is proposed to solve the static problem. Utilizing the remove-reinsert process of the LNS, the latest request nodes are regarded as a part of the removed nodes; these nodes can be inserted into the original or current solution in good time in the reinsertion process; meanwhile, its computing speed is high and effective for it does not need to resolve primal problem each time. Computational results of a large number of test problems, which cited from Solomon's static benchmarks and Lacker’s dynamic data set, show that our method is superior to other methods in most instances.