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.     

The Flexible Periodic Vehicle Routing Problem

This paper introduces the Flexible Periodic Vehicle Routing Problem (FPVRP) where a carrier has to establish a distribution plan to serve his customers over a planning horizon. Each customer has a total demand that must be served within the horizon and a limit on the maximum quantity that can be delivered at each visit. A fleet of homogeneous capacitated vehicles is available to perform the services and the objective is to minimize the total routing cost. The FPVRP can be seen as a generalization of the Periodic Vehicle Routing Problem (PVRP) which instead has fixed service frequencies and schedules and where the quantity delivered at each visit is fixed. Moreover, the FPVRP shares some common characteristics with the Inventory Routing Problem (IRP) where inventory levels are considered at each time period and, typically, an inventory cost is involved in the objective function. We present a worst-case analysis which shows the advantages of the FPVRP with respect to both PVRP and IRP. Moreover, we propose a mathematical formulation for the problem, together with some valid inequalities. Computational results show that adding flexibility improves meaningfully the routing costs in comparison with both PVRP and IRP.     

A general variable neighborhood search for the swap-body vehicle routing problem

The Swap-Body Vehicle Routing Problem, a generalization of the well known Vehicle Routing Problem, can be stated as follows: the vehicle fleet consisting of trucks, semi-trailers, and swap bodies, is available at a single depot to serve a given set of customers. To serve a subset of customers, one may use either a truck carrying one swap body or a train (a truck with a semi-trailer attached to it) carrying two swap bodies. In both cases, a vehicle (a truck or a train) must perform a route starting and ending at the depot, so to satisfy demands of visited customers, maximal allowed route duration, allowed load on the used vehicle, and accessibility constraint of each customer. The accessibility constraint indicates whether a customer is allowed to be visited by a train or not. In addition, a set of swap locations is given where semi-trailers and swap bodies may be parked or swapped. The goal of the Swap-Body Vehicle Routing Problem is to minimize the total costs consisting of the fixed costs for using vehicles and costs for performing routes. In this paper, we propose two general variable neighborhood search heuristics to solve this problem. The quality of the proposed methods is evaluated on the instances provided by the organizers of VeRolog Solver Challenge 2014.     

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.     

求解需求可拆分车辆路径问题的聚类算法

针对需求可拆分车辆路径问题（SDVRP）,提出一种先分组后路径的聚类算法。该算法考虑车辆载重的均衡性和可行解的特征,优先安排载重大于等于车辆限载的客户;然后结合客户间的距离和载重,设定一个拆分阈值限定车辆载重范围,按照就近原则对客户进行聚类分组,当组内客户载重未达到车辆载重最小值而加入新客户后超出限载时,对新加入客户进行拆分和调整,最终完成对所有客户的分组;最后采用蚁群优化算法对各组内客户进行线路规划。实验结果表明,所提算法在求解需求可拆分车辆路径问题时,具有更高的稳定性,得到的结果更优。     

A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem

We consider the Commodity constrained Split Delivery Vehicle Routing Problem (C-SDVRP), a routing problem where customers may request multiple commodities. The vehicles can deliver any set of commodities and multiple visits to a customer are allowed only if the customer requests multiple commodities. If the customer is visited more than once, the different vehicles will deliver different sets of commodities. Allowing the splitting of the demand of a customer only for different commodities may be more costly than allowing also the splitting of each individual commodity, but at the same time it is easier to organize and more acceptable to customers. We model the C-SDVRP by means of a set partitioning formulation and present a branch-price-and-cut algorithm. In the pricing phase, the ng-path relaxation of a constrained elementary shortest path problem is solved with a label setting dynamic programming algorithm. Capacity cuts are added in order to strengthen the lower bound. We solve to optimality within 2 h instances with up to 40 customers and 3 commodities per customer.     

需求可拆分车辆路径问题的禁忌搜索算法

为解决实际配送运输中的车辆路径问题（Vehicle Routing Problem,VRP）,通过改进传统的数学模型,解除每个客户需求只能由l辆车配送的约束,建立改进的可拆分车辆路径问题（Split Delivery VRP,SDVRP）数学模型,并利用禁忌搜索算法（Taboo Search Algorithm,TSA）进行求解．在TSA的设计中,根据SDVRP模型的特点对初始解、邻域搜索和解的评价等进行特殊处理．算例表明,该模型不仅可以解决VRP模型中不允许配送点需求量超出装载量的限制,而且通过相应配送点需求量的拆分和重新组合,可节省车辆数目、缩短路线长度、提高车辆装载率．     

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.     

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 customer-centric,multi-commodity vehicle routing problem with split delivery

In this paper, we present the Customer-centric, Multi-commodity Vehicle Routing Problem with Split Delivery (CMVRPSD) whose objective is to minimize total waiting time of customers in distributing multiple types of commodities by multiple capacitated vehicles. It is assumed that a customer's demand can be fulfilled by more than one vehicle. Two classes of decisions are involved in this problem: routing vehicles to customers and quantifying commodities to load and unload. The CMVRPSD can be applied to distributing commodities in customer-oriented distribution problems for both peacetime and disaster situations. The problem is formulated in two Mixed-Integer Linear Programming (MILP) models, and a heuristic method is proposed by adapting and synthesizing Simulated Annealing (SA) and Variable Neighborhood Search (VNS) for large-scale problems. Experimental results show that the proposed hybrid algorithm outperforms other applicable algorithms such as SA, VNS, and Nearest Neighborhood heuristic.     

An ILP improvement procedure for the Open Vehicle Routing Problem

We address the Open Vehicle Routing Problem (OVRP), a variant of the “classical” (capacitated and distance constrained) Vehicle Routing Problem (VRP) in which the vehicles are not required to return to the depot after completing their service. We present a heuristic improvement procedure for OVRP based on Integer Linear Programming (ILP) techniques. Given an initial feasible solution to be possibly improved, the method follows a destruct-and-repair paradigm, where the given solution is randomly destroyed (i.e., customers are removed in a random way) and repaired by solving an ILP model, in the attempt of finding a new improved feasible solution. The overall procedure can be considered as a general framework which could be extended to cover other variants of Vehicle Routing Problems. We report computational results on benchmark instances from the literature. In several cases, the proposed algorithm is able to find the new best known solution for the considered instances.     

A cooperative coevolutionary algorithm for the Multi-Depot Vehicle Routing Problem

The Multi-Depot Vehicle Routing Problem (MDVRP) is an important variant of the classical Vehicle Routing Problem (VRP), where the customers can be served from a number of depots. This paper introduces a cooperative coevolutionary algorithm to minimize the total route cost of the MDVRP. Coevolutionary algorithms are inspired by the simultaneous evolution process involving two or more species. In this approach, the problem is decomposed into smaller subproblems and individuals from different populations are combined to create a complete solution to the original problem. This paper presents a problem decomposition approach for the MDVRP in which each subproblem becomes a single depot VRP and evolves independently in its domain space. Customers are distributed among the depots based on their distance from the depots and their distance from their closest neighbor. A population is associated with each depot where the individuals represent partial solutions to the problem, that is, sets of routes over customers assigned to the corresponding depot. The fitness of a partial solution depends on its ability to cooperate with partial solutions from other populations to form a complete solution to the MDVRP. As the problem is decomposed and each part evolves separately, this approach is strongly suitable to parallel environments. Therefore, a parallel evolution strategy environment with a variable length genotype coupled with local search operators is proposed. A large number of experiments have been conducted to assess the performance of this approach. The results suggest that the proposed coevolutionary algorithm in a parallel environment is able to produce high-quality solutions to the MDVRP in low computational time.     

Lifted and Local Reachability Cuts for the Vehicle Routing Problem with Time Windows

The Vehicle Routing Problem with Time Windows (VRPTW) requires to design minimum cost routes for a fleet of vehicles with identical capacities to serve a set of customers within given time windows. Each customer must be visited exactly once and the load of a vehicle must not exceed its capacity.     

基于K均值聚类和LK算法的应急物资调度

突发性事件中应急物资调度方案最优化问题是典型的车辆路径规划（VRP）问题。对于大规模的VRP问题求解,经典的启发式算法易陷入局部最优,难以得到高质量的调度方案。针对这一问题,提出了一种基于K均值聚类和LK算法的调度方法。该方法采用K均值聚类方法将需求节点分成n个子集合,对聚类结果进行修正后分配给n辆运输车辆,采用LK算法对每辆运输车辆的运输路径进行优化。仿真实验结果表明,方法获得了较好的调度方案,而且单个运输车辆服务的需求节点个数越多,方法的优势越明显。     

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

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

基于双层模糊聚类的多车场车辆路径遗传算法

对大规模多车场车辆路径问题,设计了基于双层模糊聚类的改进遗传算法求解框架,上层静态区域划分利用k-means技术将多车场到多客户的问题转化为一对多的子问题,下层模糊聚类从保证客户满意度和整合物流资源的角度出发,利用模糊聚类算法根据客户需求属性形成基于客户订单配送的动态客户群。进一步,通过改进选择算子和交叉算子来设计车辆路径优化的遗传算法。通过随机算例仿真实验,证明了提出方法和求解策略的有效性。     

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.     

半柔性覆盖的多配送中心路线优化问题研究

为应对“双十一”“618”需求突发性爆涨下物流配送网络的爆仓、滞缓等问题,提出能够兼顾配送系统稳定性和配送路线竞争性的“半柔性覆盖策略”,研究半柔性覆盖的多配送中心路线优化问题。在传统配送中心路线优化问题的基础上,根据地理位置,区分固定需求点和柔性需求点,定义固定需求点只能由所属配送中心服务,而柔性需求点可由多个配送中心协同服务;以总成本最小为目标,建立半柔性覆盖的多配送中心路线优化模型;设计遗传算法求解,使用Matlab编译;选取申通快递在西安北郊地区的五个配送站点为实例进行求解,将求解结果与原始路线、“全柔性覆盖策略”和“固定分区策略”进行对比,验证了“半柔性覆盖策略”的有效性。     

有软时窗多车场开放式车辆路径及其禁忌搜索

有软时窗约束多车场开放式车辆路径问题是在基本的车辆路径问题上增加了时间窗约束和多车场作业的一种变化形式,是一个典型的NP-难问题。建立了问题模型,运用改进的禁忌搜索算法测试了算例。快速获得的高质量解验证了模型的正确性和算法性能的优良性。