A reactive tabu search for the vehicle routing problem

The classical vehicle routing problem (VRP) involves determining a fleet of homogeneous size vehicles and designing an associated set of routes that minimizes the total cost. Our tabu search (TS) algorithm to solve the VRP is based on reactive tabu search (RTS) with a new escape mechanism, which manipulates different neighbourhood schemes in a very sophisticated way in order to get a balanced intensification and diversification continuously during the search process. We compare our algorithm with the best methods in the literature using different data sets and report results including new best known solutions for several well-known benchmark problems.     

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.     

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.     

An exact solution framework for a broad class of vehicle routing problems

This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.     

Vehicle routing with split deliveries

This paper considers a relaxation of the classical vehicle routing problem (VRP), in which split deliveries are allowed. As the classical VRP, this problem is NP-hard, but nonetheless it seems more difficult to solve exactly. It is first formulated as an integer linear program. Several new classes of valid constraints are derived, and a hierarchy between these is established. A constraint relaxation branch and bound algorithm for the problem is then described. Computational results indicate that by using an appropriate combination of constraints, the gap between the lower and upper bounds at the root of the search tree can be reduced considerably. These results also confirm the quality of a previously published heuristic for this problem.     

Exact algorithms for the chance-constrained vehicle routing problem

We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for the VRP with stochastic demands require independent demands. We first study an edge-based formulation for the CCVRP, in particular addressing the challenge of how to determine a lower bound on the number of vehicles required to serve a subset of customers. We then investigate the use of a branch-and-cut-and-price (BCP) algorithm. While BCP algorithms have been considered the state of the art in solving the deterministic VRP, few attempts have been made to extend this framework to the VRP with stochastic demands. In contrast to the deterministic VRP, we find that the pricing problem for the CCVRP problem is strongly \(\mathcal {NP}\)-hard, even when the routes being priced are allowed to have cycles. We therefore propose a further relaxation of the routes that enables pricing via dynamic programming. We also demonstrate how our proposed methodologies can be adapted to solve a distributionally robust CCVRP problem. Numerical results indicate that the proposed methods can solve instances of CCVRP having up to 55 vertices.     

Exact algorithms for the vehicle routing problem,based on spanning tree and shortest path relaxations

We consider the problem of routing vehicles stationed at a central facility (depot) to supply customers with known demands, in such a way as to minimize the total distance travelled. The problem is referred to as the vehicle routing problem (VRP) and is a generalization of the multiple travelling salesman problem that has many practical applications. We present tree search algorithms for the exact solution of the VRP incorporating lower bounds computed from (i) shortest spanningk-degree centre tree (k-DCT), and (ii)q-routes. The final algorithms also include problem reduction and dominance tests. Computational results are presented for a number of problems derived from the literature. The results show that the bounds derived from theq-routes are superior to those fromk-DCT and that VRPs of up to about 25 customers can be solved exactly.     

求解车辆路径问题的离散蝙蝠算法

根据车辆路径问题的数学模型,分析了它的具体特征,从而对BA的操作算子又进行了重新定义,设计了求解VRP问题的离散蝙蝠算法,并通过实例测试将离散蝙蝠算法与其他算法进行比较,验证了该算法求解VRP问题的有效性与可行性.     

Heuristics for the lexicographic max-ordering vehicle routing problem

In this paper, we propose fast heuristics for the vehicle routing problem (VRP) with lexicographic max-order objective. A fixed number of vehicles, which are based at a depot, are to serve customers with known demands. The lexicographic max-order objective is introduced by asking to minimize lexicographically the sorted route lengths. Based on a model for this problem, several approaches are studied and new heuristic solution procedures are discussed resulting in the development of a sequential insertion heuristic and a modified savings algorithm in several variants. Comparisons between the algorithms are performed on instances of the VRP library VRPLIB. Finally, based on the results from the computational experiments, conclusions about the applicability and efficiency of the presented algorithms are drawn.     

A real delivery problem dealt with Monte Carlo Techniques

In this paper we use Monte Carlo Techniques to deal with a real world delivery problem of a food company in Valencia (Spain). The problem is modeled as a set of 11 instances of the well known Vehicle Routing Problem, VRP, with additional time constraints. Given that VRP is a NP-hard problem, a heuristic algorithm, based on Monte Carlo techniques, is implemented. The solution proposed by this heuristic algorithm reaches distance and money savings of about 20% and 5% respectively. This work has been partially supported by thePlan de Incentivo a la Investigación/98 of the Universidad Politécnica de Valencia, under the project “Técnicas Monte Carlo aplicadas a Problemas de Rutas de Vehículos”.     

城市配送车辆路径优化集束式算法的客户点归并策略

VRP问题的研究起步较早,求解方法也非常丰富,然而,面对客户规模庞大,交通网络复杂的多约束车辆优化调度问题,现有算法显得无能为力.为有效解决需求点规模庞大的城市配送车辆优化调度问题,提出一种新的两阶段启发式算法——集束式算法,采用"集中后分派,分派后扩展"的思想,对末梢客户和同路段客户进行客户点合并,从全局上降低搜索范围,并提出相关客户点归并算法.     

Heuristic solutions for the vehicle routing problem with time windows and synchronized visits

We present a simulated annealing based algorithm for a variant of the vehicle routing problem (VRP), in which a time window is associated with each client service and some services require simultaneous visits from different vehicles to be accomplished. The problem is called the VRP with time windows and synchronized visits. The algorithm features a set of local improvement methods to deal with various objectives of the problem. Experiments conducted on the benchmark instances from the literature clearly show that our method is fast and outperforms the existing approaches. It produces all known optimal solutions of the benchmark in very short computational times, and improves the best results for the rest of the instances.     

Vehicle routing with cross-docking

Over the past decade, cross-docking has emerged as an important material handling technology in transportation. A variation of the well-known Vehicle Routing Problem (VRP), the VRP with Cross-Docking (VRPCD) arises in a number of logistics planning contexts. This paper addresses the VRPCD, where a set of homogeneous vehicles are used to transport orders from the suppliers to the corresponding customers via a cross-dock. The orders can be consolidated at the cross-dock but cannot be stored for very long because the cross-dock does not have long-term inventory-holding capabilities. The objective of the VRPCD is to minimize the total travel time while respecting time window constraints at the nodes and a time horizon for the whole transportation operation. In this paper, a mixed integer programming formulation for the VRPCD is proposed. A tabu search heuristic is embedded within an adaptive memory procedure to solve the problem. The proposed algorithm is implemented and tested on data sets provided by the Danish consultancy Transvision, and involving up to 200 pairs of nodes. Experimental results show that this algorithm can produce high-quality solutions (less than 5% away from optimal solution values) within very short computational time.     

随机需求的车辆路线问题的新模型

本主要研究随机需求的VRP问题,其中服务需求量满足二项式分布,根据期望值的大小我们提出了在一条路线上理想最大服务点数的新概念,并在此基础上建立了三种VRP问题的新模型,由于允许服务失败两次和部分服务使得模糊能适应多种实际问题,以模拟退火思想为基础的两阶段方法经修正后用于解新模型并取得较好的数值结果,理论分析和数值结果表明,新模型较好地描述随机需求的VRP问题,并且容易求解。     

An improved ant colony optimization for vehicle routing problem

The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. This paper proposes an improved ant colony optimization (IACO), which possesses a new strategy to update the increased pheromone, called ant-weight strategy, and a mutation operation, to solve VRP. The computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches.     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

以商圈为中心的O2O动态外卖配送路径优化模型与算法

针对线上到线下(Online to Offline,O2O) 外卖路径优化问题,综合考虑其动态配送需求、货物区分等特点以及时间窗、载货量等约束条件,将商圈看作配送中心,将快递员数量与快递员总行驶时间作为最小化目标,提出了以商圈为中心的O2O动态外卖配送路径优化模型。采用周期性处理新订单的方法将相应的快递员路径的动态调整问题转化为一系列静态TSP子问题,设计了一种分阶段启发式实时配送路径优化算法框架,并给出了一个具体算法和一个数值计算实例。在VRP通用算例的基础上,以商圈为中心生成测试算例,对本文算法进行仿真实验,并与其他算法比较。结果表明：本文算法能充分利用新订单附近的快递员进行配送,并优化其配送路径,有效减少了快递员数量与快递员总行驶时间。     

A new exact algorithm for the vehicle routing problem based onq-paths andk-shortest paths relaxations

We consider the basic Vehicle Routing Problem (VRP) in which a fleet ofM identical vehicles stationed at a central depot is to be optimally routed to supply customers with known demands subject only to vehicle capacity constraints. In this paper, we present an exact algorithm for solving the VRP that uses lower bounds obtained from a combination of two relaxations of the original problem which are based on the computation ofq-paths andk-shortest paths. A set of reduction tests derived from the computation of these bounds is applied to reduce the size of the problem and to improve the quality of the bounds. The resulting lower bounds are then embedded into a tree-search procedure to solve the problem optimally. Computational results are presented for a number of problems taken from the literature. The results demonstrate the effectiveness of the proposed method in solving problems involving up to about 50 customers and in providing tight lower bounds for problems up to about 150 customers.     

煤矿物资多车型配送的改进遗传算法求解

首先根据郑州煤电物资供销有限公司的实际情况建立单车场多车型车辆路径问题的模型,在此模型的基础上,用本文提出的改进遗传算法(IGA)对其求解,最后通过和传统的启发式算法(CHA)、扫描法(SA)的求解从配送费用、配送车辆数和运算时间上进行了综合比较,得出IGA算法求得的总运输费用最低,SA算法次之,CHA算法最高;但从所需参与配送的车辆数目来看,CHA求得的最好解所需的车辆数最少,其次是SA,IGA最多;在平均计算时间上,CHA的优势最明显,仅为SA的,IGA的.     

A hybrid evolutionary algorithm for the periodic location-routing problem

The well-known vehicle routing problem (VRP) has been studied in depth over the last decades. Nowadays, generalizations of VRP have been developed for tactical or strategic decision levels of companies but not both. The tactical extension or periodic VRP (PVRP) plans a set of trips over a multiperiod horizon, subject to frequency constraints. The strategic extension is motivated by interdependent depot location and routing decisions in most distribution systems. Low-quality solutions are obtained if depots are located first, regardless of the future routes. In the location-routing problem (LRP), location and routing decisions are tackled simultaneously. Here for the first time, except for some conference papers, the goal is to combine the PVRP and LRP into an even more realistic problem covering all decision levels: the periodic LRP or PLRP. A hybrid evolutionary algorithm is proposed to solve large size instances of the PLRP. First, an individual representing an assignment of customers to combinations of visit days is randomly generated. The evolution operates through an Evolutionary Local Search (ELS) on visit day assignments. The algorithm is hybridized with a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) to create feasible solutions and stops when a given number of iterations is reached. The method is evaluated over three sets of instances, and solutions are compared to the literature on particular cases such as one-day horizon (LRP) or one depot (PVRP). This metaheuristic outperforms the previous methods for the PLRP.