Customer satisfaction in dynamic vehicle routing problem with time windows

The dynamic vehicle routing and scheduling problem is a well-known complex combinatorial optimization problem that drew significant attention over the past few years. This paper presents a novel algorithm introducing a new strategy to integrate anticipated future visit requests during plan generation, aimed at explicitly improving customer satisfaction. An evaluation of the proposed strategy is performed using a hybrid genetic algorithm previously designed for the dynamic vehicle problem with time windows that we modified to capture customer satisfaction over multiple visits. Simulations compare the value of the revisited algorithm exploiting the new strategy, clearly demonstrating its impact on customer satisfaction level.     

基于时空聚类求解带容积约束的选址-路径问题

选址-路径问题是供应链管理和物流系统规划中的一个重要问题,对总成本具有十分重要的影响.对考虑配送中心容积约束的带时间窗的选址-路径问题进行研究,建立以总成本最小和客户满意度最大为目标的多目标规划模型,提出两阶段算法对其进行求解.首先,利用k-means聚类算法确定配送中心选址;然后,提出一种基于时间-空间双因素的客户划分方法以确定配送中心所服务客户;最后,利用粒子群算法对各配送中心的配送路径进行规划.数值算例表明,所提出的算法较其他已有算法,均能有效地降低物流运作总成本及总配送路径长度,为解决带容积约束及时间窗的选址-路径问题提供了一种新的解决思路.     

考虑交通拥堵的冷链物流城市配送的GVRP研究

针对目前研究冷链物流车辆路径问题多未考虑交通拥堵对运营成本的影响,将道路拥堵因素融入到冷链物流绿色车辆路径（Green Vehicle Routing Problem）优化数学模型中。兼顾经济成本和环境成本,在时变网络下综合考虑冷链物流中车辆管理成本、运输能耗成本、货损成本、制冷成本以及客户需求时间窗的惩罚成本,同时引入运输和制冷过程中产生的碳排放成本,统筹安排车辆路径,使得物流企业整体运营成本最低,更绿色环保。在此基础上根据模型特点设计改进蚁群算法进行求解,用实例对模型和算法进行仿真,验证该模型和方法可以有效地规避拥堵时段,降低配送成本,促进物流企业的节能减排,可以为物流企业冷链配送路径决策提供良好的参考依据。     

强化学习在车辆路径问题中的研究综述

车辆路径问题是物流运输优化中的核心问题,目的是在满足顾客需求下得到一条最低成本的车辆路径规划。但随着物流运输规模的不断增大,车辆路径问题求解难度增加,并且对实时性要求也不断提高,已有的常规算法不再适应实际要求。近年来,基于强化学习算法开始成为求解车辆路径问题的重要方法,在简要回顾常规方法求解车辆路径问题的基础上,重点总结基于强化学习求解车辆路径问题的算法,并将算法按照基于动态规划、基于价值、基于策略的方式进行了分类;最后对该问题未来的研究进行了展望。     

基于划分的蚁群算法求解货物权重车辆路径问题

考虑单产品分销网络中的车辆路径问题(VRP:vehicle routing problem).与以往诸多研究不同的是,建立了一种带货物载重量的VRP模型(weighted VRP),即车辆在两个顾客之间行驶时的载重量也作为影响运输费用的一个因素考虑.因此,需求量较大的顾客拥有较高的车辆运输优先权.在分析了问题性质的基础上,提出一种基于划分策略的蚁群算法PMMAS求解货物权重车辆路径问题,并与其他常用的启发式算法进行比较分析,表明了算法的有效性.     

时间依赖型车辆路径问题的一种改进蚁群算法

时间依赖型车辆路径规划问题(TDVRP),是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化.传统车辆路径问题(VRP)已被证明是NP-hard问题,因此,考虑交通状况时变特征的TDVRP问题求解更为困难.本文设计了一种TDVRP问题的改进蚁群算法,采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解,通过局部搜索操作提高可行解的质量,采用最大--最小蚂蚁系统信息素更新策略.测试结果表明,与最邻近算法和遗传算法相比,改进蚁群算法具有更高的效率,能够得到更优的结果;对于大规模TDVRP问题,改进蚁群算法也表现出良好的性能,即使客户节点数量达到1000,算法的优化时间依然在可接受的范围内.     

A two-stage heuristic method for vehicle routing problem with split deliveries and pickups

The vehicle routing problem （VRP） is a well-known combinatorial optimization issue in transportation and logistics network systems. There exist several limitations associated with the traditional VRP. Releasing the restricted conditions of traditional VRP has become a research focus in the past few decades. The vehicle routing problem with split deliveries and pickups （VRPSPDP） is particularly proposed to release the constraints on the visiting times per customer and vehicle capacity, that is, to allow the deliveries and pickups for each customer to be simultaneously split more than once. Few studies have focused on the VRPSPDP problem. In this paper we propose a two-stage heuristic method integrating the initial heuristic algorithm and hybrid heuristic algorithm to study the VRPSPDP problem. To validate the proposed algorithm, Solomon benchmark datasets and extended Solomon benchmark datasets were modified to compare with three other popular algorithms. A total of 18 datasets were used to evaluate the effectiveness of the proposed method. The computational results indicated that the proposed algorithm is superior to these three algorithms for VRPSPDP in terms of total travel cost and average loading rate.     

配送中心多车辆集散货物路线的禁忌搜索研究

多车辆集散货物路线问题是客户可以同时取货和发货,而且客户发货量在路线安排前是不确定的。提出了一种改进的禁忌搜索算法,该算法将路径问题按不同的车辆-顾客分配结构分解成若干子问题,然后用禁忌搜索算法求解每个子问题,最后从所有子问题的最优解中选出全局最优解。     

Multi-start simulated annealing heuristic for the location routing problem with simultaneous pickup and delivery

The location routing problem with simultaneous pickup and delivery (LRPSPD) is a new variant of the location routing problem (LRP). The objective of LRPSPD is to minimize the total cost of a distribution system including vehicle traveling cost, depot opening cost, and vehicle fixed cost by locating the depots and determining the vehicle routes to simultaneously satisfy the pickup and the delivery demands of each customer. LRPSPD is NP-hard since its special case, LRP, is NP-hard. Thus, this study proposes a multi-start simulated annealing (MSA) algorithm for solving LRPSPD which incorporates multi-start hill climbing strategy into simulated annealing framework. The MSA algorithm is tested on 360 benchmark instances to verify its performance. Results indicate that the multi-start strategy can significantly enhance the performance of traditional single-start simulated annealing algorithm. Our MSA algorithm is very effective in solving LRPSPD compared to existing solution approaches. It obtained 206 best solutions out of the 360 benchmark instances, including 126 new best solutions.     

An effective memetic algorithm for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a transportation problem which occurs when the objective is to minimize the sum of arrival times at customers, instead of the classical route length, subject to vehicle capacity constraints. This type of challenges arises whenever priority is given to the satisfaction of the customer need, e.g. vital goods supply or rescue after a natural disaster. The CCVRP generalizes the NP-hard traveling repairman problem (TRP), by adding capacity constraints and a homogeneous vehicle fleet. This paper presents the first upper and lower bounding procedures for this new problem. The lower bounds are derived from CCVRP properties. Upper bounds are given by a memetic algorithm using non-trivial evaluations of cost variations in the local search. Good results are obtained not only on the CCVRP, but also on the special case of the TRP, outperforming the only TRP metaheuristic published.     

A label based ant colony algorithm for heterogeneous vehicle routing with mixed backhaul

Vehicle heterogeneity and backhaul mixed-load problems are often studied separately in existing literature. This paper aims to solve a type of vehicle routing problem by simultaneously considering fleet heterogeneity, backhaul mixed-loads, and time windows. The goal is to determine the vehicle types, the fleet size, and the travel routes such that the total service cost is minimized. We propose a multi-attribute Label-based Ant Colony System (LACS) algorithm to tackle this complex optimization problem. The multi-attribute labeling technique enables us to characterize the customer demand, the vehicle states, and the route options. The features of the ant colony system include swarm intelligence and searching robustness. A variety of benchmark instances are used to demonstrate the computational advantage and the global optimality of the LACS algorithm. We also implemented the proposed algorithm in a real-world environment by solving an 84-node postal shuttle service problem for China Post Office in Guangzhou. The results show that a heterogeneous fleet is preferred to a homogenous fleet as it generates more cost savings under variable customer demands.     

考虑时效性和品质性满意度约束的易腐品冷链物流配送

针对易腐品冷链配送环节存在的成本高、碳排放量大、客户满意度低等问题,从易腐品配送的时效性和品质性两方面度量客户满意度,并以此为约束考虑配送过程中的固定成本、运输成本、货损成本、制冷成本、惩罚成本以及碳排放成本,构建以总成本最小为目标的易腐品冷链配送车辆路径优化模型,设计改进遗传算法求解优化模型,分析求解算法的复杂度.数值实验结果表明,所设计的求解算法总能获得总成本更低、产品新鲜度更高以及碳排放量更少的配送方案,同时表明改进的遗传算法相比于传统遗传算法在成本节约以及客户满意度提高方面具有一定优势,在一定程度上验证了所建模型的合理性及求解算法的有效性.     

基于遗传算法的多目标的有时间窗的车辆调度

对传统有时间窗的车辆优化调度问题进行了分析，指出了其中存在的问题。提出了一个以最大的顾客满意度和最小的费用为目标的多目标模型，给出了具体的操作步骤。从遗传算法的角度分析了该模型在最坏和最好情况下的时间复杂度。仿真结果和在某物流公司的实际应用证明该算法是可行的，且有较好的时间和优化性能。     

前摄性车辆路径问题及其遗传算法求解

通过对现有文献中需求信息不确定的动态车辆路径问题，在不确定需求预测和求解算法的基础上，建立了多维数据层客户需求预测方法和前摄性实时控制方法，讨论了潜在客户的响应准则。以总运输成本最小为目标，构建了引入前摄性实时控制方法求解动态车辆路径问题的数学模型，改进了遗传算法对该模型进行求解。应用京东在重庆地区的客户点的配送数据及两阶段综合前摄性调整策略，验证了设计算法的性能，实验结果表明设计的模型及算法可以对客户需求进行更及时有效的响应。     

An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows

The vehicle routing problem with simultaneous pickups and deliveries and time windows (VRP-SPDTW) is the problem of optimally integrating forward (good distribution) and reverse logistics (returning materials) for cost saving and environmental protection. We constructed a general mixed integer programming model of VRP-SPDTW. The model contained some classical vehicle routing problems as special cases. We proposed an improved differential evolution algorithm (IDE) for solving this problem. In the algorithm, we firstly adopted the novel decimal coding to construct an initial population, then used some improved differential evolution operators unlike the existing algorithm, and in mutation operation, we used an integer order criterion based on natural number coding method. We introduced a penalty technical to publish the infeasible solution. In addition, in the crossover operation, we designed a self-adapting crossover probability that varied with iteration. We did some numerical experiments, and the results showed that the proposed method is effective for solving VRP-SPDTW.     

Integrated production and delivery with single machine and multiple vehicles

This paper considers a class of multi-objective production–distribution scheduling problem with a single machine and multiple vehicles. The objective is to minimize the vehicle delivery cost and the total customer waiting time. It is assumed that the manufacturer’s production department has a single machine to process orders. The distribution department has multiple vehicles to deliver multiple orders to multiple customers after the orders have been processed. Since each delivery involves multiple customers, it involves a vehicle routing problem. Most previous research work attempts at tackling this problem focus on single-objective optimization system. This paper builds a multi-objective mathematical model for the problem. Through deep analysis, this paper proposes that for each non-dominated solution in the Pareto solution set, the orders in the same delivery batch are processed contiguously and their processing order is immaterial. Thus we can view the orders in the same delivery batch as a block. The blocks should be processed in ascending order of the values of their average workload. All the analysis results are embedded into a non-dominated genetic algorithm with the elite strategy (PD-NSGA-II). The performance of the algorithm is tested through random data. It is shown that the proposed algorithm can offer high-quality solutions in reasonable time.     

面向最小碳排放量的接送机场服务的车辆路径与调度

车辆路径与调度问题 (Vehicle routing and scheduling problem, VRSP)是制造系统自动化和商业服务系统优化调度要解决的重要问题, 常常以路径最短或成本(时间)最小为 优化目标. 在强制性碳排放政策的影响下, 如何通过路径优化与调度实现系统的节能减排, 已经成为管理者一个优化控制的目标. 本文 建立了针对接送机场服务中以最小碳排放量为目标的车次分配与调度问 题的0-1混合整数规划模型, 采用了改进的基于时间和地域划分的极线扫描算法. 重点通过不同类型、规模测试实例, 分别从测试实例的 顾客点位置分布、顾客规模以及车辆容量大小、满意度水平分析了对人均 碳排放的影响程度, 对现实接送机场服务运作中车辆配置和设置服务水平提供了有价值的建议.     

基于头脑风暴算法的电动货车路径优化问题

针对电动货车路径优化问题,应用物流网络以及电动货车电量消耗等方面的知识,研究了电动货车的智能调度方法,构建了带时间窗的电动货车路径优化模型(electric vehicle routing problem with time window,EVRPTW)。该模型考虑了耗电量与电动货车行驶速度、载重量之间的关系,客户满意度与软时间窗之间的关系。同时,引入了计算机智能算法,充分利用了遗传算法、头脑风暴算法等优化算法的智能化特征,有效提高了电动货车的配送效率。仿真结果表明:该模型运用头脑风暴算法的最优值精确度和收敛速度都优于遗传算法,可以有效解决EVRPTW问题。所提出的模型和算法能明显提高配送中心的配送效率,节省充电成本,提高顾客满意度。针对配送中心电动货车运营调度管理的特点,借助计算机技术以及自动控制技术,进一步提高了电动货车的配送效率,为物流网络系统的智能化调度提供技术准备。     

城市物流配送的混合车辆路径规划模型与优化算法

针对城市部分区域限行、物流系统中燃油车与电动车同时并存的实际情况,综合考虑客户需求量、服务时间、电动车行驶里程、已有充电设施、部分充电策略、燃油车油耗与碳排放等因素,以车辆使用固定成本、驾驶员工资、电动车的充电成本、燃油车的油耗与碳排放成本之和最小为目标构建混合车辆路径规划模型.根据模型特征设计一种改进蚁群算法求解,并采用多类型算例进行实验.实验结果表明,所提方法能在非常短的时间内给出符合决策者目标的混合车辆路径规划方案,有效降低总配送成本,减少燃油车油耗与碳排放,具有合理性、可行性与有效性.     

易腐生鲜货品车辆路径问题的改进混合蝙蝠算法

针对配送易腐生鲜货品的车辆其配送路径的选择不仅受货品类型、制冷环境变化、车辆容量限制、交货时间等多种因素的影响,而且需要达到一定的目标（如：费用最少、客户满意度最高）,构建了易腐生鲜货品车辆路径问题（VRP）的多目标模型,并提出了求解该模型的改进混合蝙蝠算法。首先,采用时间窗模糊化处理方法定义客户满意度函数,细分易腐生鲜货品类型并定义制冷成本,建立了最优路径选择的多目标模型;然后,在分析蝙蝠算法求解离散问题易陷入局部最优、过早收敛等问题的基础上,精简经典蝙蝠算法的速度更新公式,并对混合蝙蝠算法的单多点变异设定选择机制,提高算法性能;最后,对改进混合蝙蝠算法进行性能测试。实验结果表明,与基本蝙蝠算法和已有混合蝙蝠算法相比,所提算法在求解VRP时能够提高客户满意度1.6%~4.2%,且减小平均总成本0.68%~2.91%。该算法具有计算效率高、计算性能好和较高的稳定性等优势。