有数量限制的开放式车辆路径加速算法

设计有数量限制的开放式车辆路径加速禁忌搜索算法,将所有点(包括客户和仓库)做Delaunay三角剖分后,限制问题的解的大多数边与Delaunay三角剖分的边重合。实验结果表明,该算法在保证寻求到相对较优解的前提下,执行速度得到大幅度的提升,解与上界关联紧密,可以应用到其他启发式搜索问题的求解中。     

The min–max split delivery multi-depot vehicle routing problem with minimum service time requirement

The min–max Split Delivery Multi-Depot Vehicle Routing Problem with Minimum Service Time Requirement (min–max SDMDVRP-MSTR) is a variant of the Multi-Depot Vehicle Routing Problem. Each customer requires a specified amount of service time. The service time can be split among vehicles as long as each vehicle spends a minimum amount of service time at a customer. The objective is to minimize the duration of the longest route (where duration is the sum of travel and service times).We develop a heuristic (denoted by MDS) that solves the min–max SDMDVRP-MSTR in three stages: (1) initialize a feasible solution without splits; (2) improve the longest routes by splitting service times; (3) ensure all minimum service time requirements are satisfied. The first stage of MDS is compared to an existing heuristic to solve the min–max Multi-Depot Vehicle Routing Problem on 43 benchmark instances. MDS produces 37 best-known solutions. We also demonstrate the effectiveness of MDS on 21 new instances whose (near) optimal solutions can be estimated based on geometry. Finally, we investigate the savings from split service and the split patterns as we vary the required service times, the average number of customers per route, and the minimum service time requirement.     

A lower bound for the Node,Edge, and Arc Routing Problem

The Node, Edge, and Arc Routing Problem (NEARP) was defined by Prins and Bouchenoua in 2004, although similar problems have been studied before. This problem, also called the Mixed Capacitated General Routing Problem (MCGRP), generalizes the classical Capacitated Vehicle Routing Problem (CVRP), the Capacitated Arc Routing Problem (CARP), and the General Routing Problem. It captures important aspects of real-life routing problems that were not adequately modeled in previous Vehicle Routing Problem (VRP) variants. The authors also proposed a memetic algorithm procedure and defined a set of test instances called the CBMix benchmark. The NEARP definition and investigation contribute to the development of rich VRPs. In this paper we present the first lower bound procedure for the NEARP. It is a further development of lower bounds for the CARP. We also define two novel sets of test instances to complement the CBMix benchmark. The first is based on well-known CARP instances; the second consists of real life cases of newspaper delivery routing. We provide numerical results in the form of lower and best known upper bounds for all instances of all three benchmarks. For three of the instances, the gap between the upper and lower bound is closed. The average gap is 25.1%. As the lower bound procedure is based on a high quality lower bound procedure for the CARP, and there has been limited work on approximate solution methods for the NEARP, we suspect that a main reason for the rather large gaps is the quality of the upper bound. This fact, and the high industrial relevance of the NEARP, should motivate more research on approximate and exact methods for this important problem.     

Improved bounds for large scale capacitated arc routing problem

The Capacitated Arc Routing Problem (CARP) stands among the hardest combinatorial problems to solve or to find high quality solutions. This becomes even more true when dealing with large instances. This paper investigates methods to improve on lower and upper bounds of instances on graphs with over 200 vertices and 300 edges, dimensions that, today, can be considered of large scale. On the lower bound side, we propose to explore the speed of a dual ascent heuristic to generate capacity cuts. These cuts are next improved with a new exact separation enchained to the linear program resolution that follows the dual heuristic. On the upper bound, we implement a modified Iterated Local Search procedure to Capacitated Vehicle Routing Problem (CVRP) instances obtained by applying a transformation from the CARP original instances. Computational experiments were carried out on the set of large instances generated by Brandão and Eglese and also on the regular size sets. The experiments on the latter allow for evaluating the quality of the proposed solution approaches, while those on the former present improved lower and upper bounds for all instances of the corresponding set.     

需求可拆分的开放式车辆路径问题研究

传统的开放式车辆路径问题假设客户的需求不可拆分、车辆类型相同,但在实际的物流配送中,车辆类型不完全相同,对需求的拆分能充分利用车辆的装载能力,降低运输成本。为此,提出需求可拆分的不同种车辆的开放式车辆路径问题,给出整数规划的数学模型,利用禁忌搜索算法对该问题求解,改进算法中初始解和邻域结构的产生过程。通过实验验证模型的有效性,并将结果与传统的开放式车辆路径问题进行比较,表明该算法可有效减少运输成本。     

Hybrid metaheuristics for the Clustered Vehicle Routing Problem

The Clustered Vehicle Routing Problem (CluVRP) is a variant of the Capacitated Vehicle Routing Problem in which customers are grouped into clusters. Each cluster has to be visited once, and a vehicle entering a cluster cannot leave it until all customers have been visited. This paper presents two alternative hybrid metaheuristic algorithms for the CluVRP. The first algorithm is based on an Iterated Local Search algorithm, in which only feasible solutions are explored and problem-specific local search moves are utilized. The second algorithm is a hybrid genetic search, for which the shortest Hamiltonian path between each pair of vertices within each cluster should be precomputed. Using this information, a sequence of clusters can be used as a solution representation and large neighborhoods can be efficiently explored, by means of bi-directional dynamic programming, sequence concatenation, and appropriate data structures. Extensive computational experiments are performed on benchmark instances from the literature, as well as new large scale instances. Recommendations on the choice of algorithm are provided, based on average cluster size.     

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.     

School bus routing—a column generation approach

The School Bus Routing Problem (SBRP), a generalization of the well‐known Vehicle Routing Problem, involves the routing, planning, and scheduling of public school bus transportation. The problem can be divided into several subproblems, including bus stop selection, assigning students to buses, and determining the bus routes. This work presents an exact branch‐and‐price framework for the SBRP, with a strong emphasis on efficiency issues inherently related to column generation (CG). Experiments are conducted on a set of 128 SBRP instances. Many of these instances are solved optimally; for the remaining instances, strong lower bounds have been derived. Furthermore, better integer solutions were found for a number of instances reported in the literature. Both lower bounds computed on the optimum solution and stabilization added to the CG procedure significantly improved computation times.     

An adaptive local search algorithm for vehicle routing problem with simultaneous and mixed pickups and deliveries

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is an extension to the classical Vehicle Routing Problem (VRP), where customers may both receive and send goods simultaneously. The Vehicle Routing Problem with Mixed Pickup and Delivery (VRPMPD) differs from the VRPSPD in that the customers may have either pickup or delivery demand. However, the solution approaches proposed for the VRPSPD can be directly applied to the VRPMPD. In this study, an adaptive local search solution approach is developed for both the VRPSPD and the VRPMPD, which hybridizes a Simulated Annealing inspired algorithm with Variable Neighborhood Descent. The algorithm uses an adaptive threshold function that makes the algorithm self-tuning. The proposed approach is tested on well-known VRPSPD and VRPMPD benchmark instances derived from the literature. The computational results indicate that the proposed algorithm is effective in solving the problems in reasonable computation time.     

A hybrid clonal selection algorithm for the location routing problem with stochastic demands

In this paper, a new formulation of the Location Routing Problem with Stochastic Demands is presented. The problem is treated as a two phase problem where in the first phase it is determined which depots will be opened and which customers will be assigned to them while in the second phase, for each of the open depots a Vehicle Routing Problem with Stochastic Demands is solved. For the solution of the problem a Hybrid Clonal Selection Algorithm is applied, where, in the two basic phases of the Clonal Selection Algorithm, a Variable Neighborhood Search algorithm and an Iterated Local Search algorithm respectively have been utilized. As there are no benchmark instances in the literature for this form of the problem, a number of new test instances have been created based on instances of the Capacitated Location Routing Problem. The algorithm is compared with both other variants of the Clonal Selection Algorithm and other evolutionary algorithms.     

带时间窗车辆路径问题的混合改进型蚂蚁算法

带时间窗车辆路径问题（VRPTW）是VRP的一种重要扩展类型,在蚂蚁算法思想基础上,设计用于求解该问题的混合改进型算法并求解Solomon标准数据库中的大量实例。经过大量数据测试并与其他启发式算法所得结果进行比较,获得了较好的效果。     

An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics

In this paper, we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP). The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm outperforms existing solution methods for the 2E-VRP and achieves excellent results on the LRP.     

带时间窗车辆路径问题的改进蚁群算法研究

针对带时间窗车辆路径问题,论文通过增加虚拟配送中心的数量,改进蚁群算法,从而将VRPTW问题转化为TSP问题进行求解,使每只蚂蚁都可以构建一条可行路径,避免在该问题中以往常由多只蚂蚁协同合作来构造解的低效性,通过实验计算表明该方法是可行的。     

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.     

Adaptive memory programming for the vehicle routing problem with multiple trips

The Vehicle Routing Problem with Multiple Trips is an extension of the classical Vehicle Routing Problem in which each vehicle may perform several routes in the same planning period. In this paper, an adaptive memory algorithm to solve this problem is proposed. Computational experience is reported over a set of benchmark problem instances.     

The Multiple Trip Vehicle Routing Problem with Backhauls: Formulation and a Two-Level Variable Neighbourhood Search

In this paper a new VRP variant the Multiple Trip Vehicle Routing Problem with Backhauls (MT-VRPB) is investigated. The classical MT-VRP model is extended by including the backhauling aspect. An ILP formulation of the MT-VRPB is first presented and CPLEX results for small and medium size instances are reported. For large instances of the MT-VRPB a Two-Level VNS algorithm is developed. To gain a continuous balanced intensification and diversification during the search process VNS is embedded with the sequential VND and a multi-layer local search approach. The algorithm is tested on a set of new MT-VRPB data instances which we generated. Interesting computational results are presented. The Two-Level VNS produced excellent results when tested on the special variant of the VRPB.     

An Adaptive Large Neighborhood Search for an E-grocery Delivery Routing Problem

Online shopping has become ever more indispensable to many people with busy schedules who have a growing need for services ranging for a wide variety of goods, which include standard (or “staple”) goods as well as “premium” goods, i.e. goods such as organic food, specialty gifts, etc. that offer higher value to consumers and higher profit margins to retailers. In this paper, we introduce a new mathematical programming formulation and present an efficient solution approach for planning the delivery services of online groceries to fulfill this diverse consumer demand without incurring additional inventory costs. We refer to our proposed model as the E-grocery Delivery Routing Problem (EDRP) as it generically represents a family of problems that an online grocery is likely to face. The EDRP is based on a distribution network where premium goods are acquired from a set of external vendors at multiple locations in the supply network and delivered to customers in a single visit. To solve this problem, we develop an improved Adaptive Large Neighborhood Search (ALNS) heuristic by introducing new removal, insertion, and vendor selection/allocation mechanisms. We validate the performance of the proposed ALNS heuristic through an extensive computational study using both the well-known Vehicle Routing Problem with Time Windows instances of Solomon and a set of new benchmark instances generated for the EDRP. The results suggest that the proposed solution methodology is effective in obtaining high quality solutions fast.     

Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem

Multi Compartment Vehicle Routing Problem is an extension of the classical Capacitated Vehicle Routing Problem where different products are transported together in one vehicle with multiple compartments. Products are stored in different compartments because they cannot be mixed together due to differences in their individual characteristics. The problem is encountered in many industries such as delivery of food and grocery, garbage collection, marine vessels, etc. We propose a hybridized algorithm which combines local search with an existent ant colony algorithm to solve the problem. Computational experiments are performed on new generated benchmark problem instances. An existing ant colony algorithm and the proposed hybridized ant colony algorithm are compared. It was found that the proposed ant colony algorithm gives better results as compared to the existing ant colony algorithm.     

基于客户满意度的开放式车辆路径问题研究

将客户满意度作为优化目标引入开放式车辆路径问题。使用梯形模糊数表示客户满意度,建立基于客户满意度的开放式车辆路径问题的数学模型。将改进的最邻近插入法和最廉价插入法作为后优化过程与粒子群优化算法结合求解该问题。分析2种混合算法的计算复杂度,通过实验仿真对算法进行分析比较。     

An open source Spreadsheet Solver for Vehicle Routing Problems

The Vehicle Routing Problem (VRP) is one of the most frequently encountered optimization problems in logistics, which aims to minimize the cost of transportation operations by a fleet of vehicles operating out of a base. This paper introduces VRP Spreadsheet Solver, an open source Excel based tool for solving many variants of the Vehicle Routing Problem (VRP). Case studies of two real-world applications of the solver from the healthcare and tourism sectors that demonstrate its use are presented. The solution algorithm for the solver, and computational results on benchmark instances from the literature are provided. The solver is found to be capable of solving Capacitated VRP and Distance-Constrained VRP instances with up to 200 customers within 1 h of CPU time.