A tabu search algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions

In this paper, we consider a periodic vehicle routing problem that includes, in addition to the classical constraints, the possibility of a vehicle doing more than one route per day, as long as the maximum daily operation time for the vehicle is not exceeded. In addition, some constraints relating to accessibility of the vehicles to the customers, in the sense that not every vehicle can visit every customer, must be observed. We refer to the problem we consider here as the site-dependent multi-trip periodic vehicle routing problem. An algorithm based on tabu search is presented for the problem and computational results presented on randomly generated test problems that are made publicly available. Our algorithm is also tested on a number of routing problems from the literature that constitute particular cases of the proposed problem. Specifically we consider the periodic vehicle routing problem; the site-dependent vehicle routing problem; the multi-trip vehicle routing problem; and the classical vehicle routing problem. Computational results for our tabu search algorithm on test problems taken from the literature for all of these problems are presented.     

基于低碳排放的车辆路径优化问题研究

研究了基于低碳排放的锦州JS配送公司的车辆路径优化问题.首先通过分析目前锦州JS配送公司的车辆路径规划方案发现该公司在规划路径时只关注路径最短,而忽视了碳排放成本.然后通过具体分析配送过程中能源消耗的来源,考虑车辆自重和载重、车辆出行距离等对配送能源消耗的影响,建立了以极小化碳排放成本为目标的车辆路径优化问题的混合整数规划模型,通过求解模型得到新的配送路径优化方案.优化后的配送方案比原先的配送方案减少了14.16万元的碳排放成本.研究结果对物流企业降低碳排放具有指导意义.     

成品油配送多车舱车辆指派及路径优化问题研究

针对成品油配送中多车型、多车舱的车辆优化调度难题,综合考虑多车型车辆指派、多车舱车辆装载及路径安排等决策,以派车成本与油耗成本之和的总成本最小为目标,建立了多车型多车舱的车辆优化调度模型。为降低模型求解的复杂性,本文提出一种基于C-W节约算法的“需求拆分→合并装载”的车辆装载策略,并综合利用Relocate和Exchange算子进行并行邻域搜索改进,获得优化的成品油配送方案。最后,通过算例验证了本文提出的模型与算法用于求解大规模成品油配送问题的有效性。并通过数据实验揭示了以下规律:1)多车舱车辆相对于单车舱车辆在运营成本上具有优越性;2)大型车辆适合远距离配送,小型车辆适合近距离配送;3)多车型车辆混合配送相对于单车型车辆配送在运营成本上具有优越性。这些规律可为成品油配送公司的车辆配置提供决策参考。     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

Finished-vehicle transporter routing problem solved by loading pattern discovery

This work addresses a new transportation problem in outbound logistics in the automobile industry: the finished-vehicle transporter routing problem (FVTRP). The FVTRP is a practical routing problem with loading constraints, and it assumes that dealers have deterministic demands for finished vehicles that have three-dimensional irregular shapes. The problem solution will identify optimal routes while satisfying demands. In terms of complex packing, finished vehicles are not directly loaded into the spaces of transporters; instead, loading patterns matching finished vehicles with transporters are identified first by mining successful loading records through virtual and manual loading test procedures, such that the packing problem is practically solved with the help of a procedure to discover loading patterns. This work proposes a mixed-integer linear programming (MILP) model for the FVTRP considering loading patterns. As a special class of routing models, the FVTRP is typically difficult to solve within a manageable computing time. Thus, an evolutionary algorithm is designed to solve the FVTRP. Comparisons of the proposed algorithm and a commercial MILP solver demonstrate that the proposed algorithm is more effective in solving medium- and large-scale problems. The proposed scheme for addressing the FVTRP is illustrated with an example and tested with benchmark instances that are derived from well-studied vehicle routing datasets.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

Solving symmetric vehicle routing problems asymmetrically

The vehicle routing problem can be regarded as a traveling salesman problem with additional constraints. Algorithms based on assignment relaxations provide better solutions for the symmetric traveling salesman problem if they are used on an asymmetric transformed distance matrix, as shown by Jonker et al., in a paper in Operations Research. The generalization of such a transformation to the distance matrix of symmetric vehicle routing problems is described. The approach is illustrated within a heuristic algorithm, although it can also be the basis for an exact algorithm. For a number of standard problems computational results are given, that are competitive to results of other algorithms.     

Research on the vehicle routing problem with interval demands

In this paper, a vehicle routing problem with interval demands is investigated based on the motivation of dispatching vehicles to deliver perishable products in practice. A nonlinear interval-based programming method is used to build a model for the vehicle routing problem with interval demands, which assumes that demands of customers are uncertain but fall in given intervals and actual demand of a customer becomes known only when the vehicle visited the customer. A vehicle-coordinated strategy was designed to solve the service failure problem. A hybrid algorithm based on the artificial immune system is also proposed to solve the model for vehicle routing problem with interval demands. The validity of methods and sensitivity analysis are illustrated by conducting some numerical examples. We find that the tolerant possibility degree of interval number has significant impacts on the distances. The planned distance strictly increased, while the additional distance strictly decreased and the total distance after coordinated transport has a U-typed relationship with the tolerant possibility degree of interval number.     

A customer-centric routing problem with multiple trips of a single vehicle

In this study, we introduce a routing problem with multiple uses of a single vehicle and service time in demand points, minimizing the sum of clients’ waiting time to receive service. This problem is relevant in the distribution of aid in disaster-stricken communities, in the recollection and/or delivery of perishable goods and personnel transportation, among other situations, where reaching clients to perform service, fast and fair, is a priority. We consider vehicle capacity and travel distance constraints, forcing multiple use of the vehicle during the planning horizon. This paper presents two mixed integer formulations for this problem, based on a multi-level network, as well as a metaheuristic algorithm. The proposed models can solve to optimality instances with up to 30 clients. The proposed metaheuristic algorithm obtains high-quality solutions in short computational times.     

A new hybrid genetic algorithm for the capacitated vehicle routing problem

Recently proved successful for variants of the vehicle routing problem (VRP) involving time windows, genetic algorithms have not yet shown to compete or challenge current best search techniques in solving the classical capacitated VRP. A new hybrid genetic algorithm to address the capacitated VRP is proposed. The basic scheme consists in concurrently evolving two populations of solutions to minimize total travelled distance using genetic operators combining variations of key concepts inspired from routing techniques and search strategies used for a time variant of the problem to further provide search guidance while balancing intensification and diversification. Results from a computational experiment over common benchmark problems report the proposed approach to be very competitive with the best-known methods.     

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems. This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.     

基于多候选储位的存取路径优化问题研究

针对单储位储存方式可能导致仓库存取通道拥挤和作业效率低的情形,提出了一种基于多候选储位的存取路径优化方法。首先分配了货物的存取储位,然后建立了多候选储位的车辆路径问题(MLVRP)模型,并基于储位优先解码原则设计了遗传算法,最后通过算例证明该方法的有效性和算法的高效性。多候选储位的方法可以为取货任务至少节约18.4%(两个候选储位)和21.8%(三个候选储位)的路程,算法迭代10000次只需要434s。     

A Lagrangean relaxation heuristic for vehicle routing

This paper presents a new heuristic algorithm for the vehicle routing problem (VRP) which makes use of Lagrangean relaxation to transform the VRP into a modified m-traveling salesman problem. Application of the proposed algorithm to test problems from the literature has produced new best-known solutions.     

A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands

This article introduces a new exact algorithm for the capacitated vehicle routing problem with stochastic demands (CVRPSD). The CVRPSD can be formulated as a set partitioning problem and it is shown that the associated column generation subproblem can be solved using a dynamic programming scheme. Computational experiments show promising results.     

不可恢复道路堵塞路径选择问题及其算法

针对不可恢复道路堵塞的路径选择问题，分析了堵塞发生的不同起始时间对通过被堵塞边的费用(时间)产生的影响，这种影响引起的后效性使得这个问题不适合用动态规划中逆序推算方法求解。本设计了一种算法(MDA)，对经典的Dijkstra算法中的权值计算进行了修正，证明了算法的复杂性为O(n^2)，并用该算法对模型进行了求解。最后通过一个算例分析，对算法进行了验证。     

一类新的车辆路径问题及其两阶段算法

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法：两阶段算法. 最后在改进的Solomn的算例的基础上,进行了数值试验.     

需求可分的车辆路径问题模型与算法

需求可分的车辆路径问题(SDVRP)无论是从运输距离还是派车数量上,都可进一步优化传统的车辆路径问题。为了降低SDVRP的求解难度,本文在分析最优解性质的基础上,加强模型的约束条件,将原模型转变为等价的改进SDVRP,并在使用蚂蚁算法求解改进SDVRP模型的过程中,采用开发新路径和2-opt相结合的方法,以避免出现迭代停滞的现象。实验表明,算法计算结果稳定,最差解与最好解的偏差仅为1.80%。     

Creating very large scale neighborhoods out of smaller ones by compounding moves

This paper discusses neighborhood search algorithms where the size of the neighborhood is “very large” with respect to the size of the input data. We concentrate on such a very large scale neighborhood (VLSN) search technique based on compounding independent moves (CIM) such as 2-opts, swaps, and insertions. We present a systematic way of creating and searching CIM neighborhoods for routing problems with side constraints. For such problems, the exact search of the CIM neighborhood becomes NP-hard. We introduce a multi-label shortest path algorithm for searching these neighborhoods heuristically. Results of a computational study on the vehicle routing problem with capacity and distance restrictions shows that CIM algorithms are very competitive approaches for solving vehicle routing problems. Overall, the solutions generated by the CIM algorithm have the best performance among the current solution methodologies in terms of percentage deviation from the best-known solutions for large-scale capacitated VRP instances.     

A tabu search algorithm for the single vehicle routing allocation problem

In the single vehicle routing allocation problem (SVRAP) we have a single vehicle, together with a set of customers, and the problem is one of deciding a route for the vehicle (starting and ending at given locations) such that it visits some of the customers. Customers not visited by the vehicle can either be allocated to a customer on the vehicle route, or they can be isolated. The objective is to minimize a weighted sum of routing, allocation and isolation costs. One special case of the general SVRAP is the median cycle problem, also known as the ring star problem, where no isolated vertices are allowed. Other special cases include the covering tour problem, the covering salesman problem and the shortest covering path problem. In this paper, we present a tabu search algorithm for the SVRAP. Our tabu search algorithm includes aspiration, path relinking and frequency-based diversification. Computational results are presented for test problems used previously in the literature and our algorithm is compared with the results obtained by other researchers. We also report results for much larger problems than have been considered by others.     

Disruption management of the vehicle routing problem with vehicle breakdown

This paper introduces a new class of problem, the disrupted vehicle routing problem (VRP), which deals with the disruptions that occur at the execution stage of a VRP plan. The paper then focuses on one type of such problem, in which a vehicle breaks down during the delivery and a new routing solution needs to be quickly generated to minimise the costs. Two Tabu Search algorithms are developed to solve the problem and are assessed in relation to an exact algorithm. A set of test problems has been generated and computational results from experiments using the heuristic algorithms are presented.