LP-based heuristics for multi-objective capacitated vehicle routing problem and arrival time prediction method for delivery trucks

A Delivery Planning and Scheduling (DPS) system is very important for logistics service providers and manufacturers that own a fleet of vehicles. This research develops a DPS system for Small- to Medium-sized Enterprise (SME) companies to plan delivery routes of vehicles and schedule arrival times at customers. The DPS system is developed based on two methods, including a Linear Programming-based Cluster-First Route-Second (LP-based CFRS) heuristic and a Delivery Route and Arrival Time Planning (DRATP) method.First, the LP-based CFRS heuristic is proposed to efficiently plan delivery routes of vehicles, for a Multi-Objective Capacitated Vehicle Routing Problem (MOCVRP). The objectives of the MOCVRP include (1) minimizing the total fleet operating costs (i.e., fuel consumption cost and driver overtime cost), (2) Assigning drivers to deliver and assist customers who have high personal relationships with them, (3) balancing delivery weights among vehicles, and (4) minimizing the amount of carbon dioxide emissions. Four LP clustering models, including three individual clustering models and one compromise-solution clustering model, are developed to group customers into clusters. One LP routing model is developed, to sequence customers in each cluster to form a delivery route that starts and ends at the depot.Then, the DRATP method is proposed to accurately schedule arrival times at customers for each vehicle, considering road restrictions, traffic congestion, travel times with traffic conditions, and drivers’ behaviors. Three techniques involved drivers’ behaviors are proposed to improve the accuracy of arrival times. The DRATP method allows interactive decisions between planners and application software.From a real case study, the results show that the proposed LP-based CFRS heuristic efficiently plan delivery routes of vehicles. It compromises the four objectives and requires a reasonable computational time. However, the proposed LP-based CFRS heuristic does not provide accurate arrival times at customers, since it uses constant travel times. From another real case study, the results show that the proposed DRATP method accurately determines arrival times at customers for each vehicle. The DRATP method that considers drivers’ behaviors improves the accuracy of arrival times about 50% over the DRATP method without considering drivers’ behaviors.

配送规划与调度（Delivery Planning and Scheduling, DPS）系统对于拥有自有车辆车队的物流服务提供商与制造商而言至关重要。本研究针对中小型企业（Small- to Medium-sized Enterprise, SME）开发了一款DPS系统，用于规划车辆配送路径并调度车辆抵达客户处的时间。该系统基于两类核心方法构建，分别为基于线性规划的聚类优先路径后推（Linear Programming-based Cluster-First Route-Second, LP-based CFRS）启发式算法，以及配送路径与到达时间规划（Delivery Route and Arrival Time Planning, DRATP）方法。
首先，针对多目标带容量约束车辆路径问题（Multi-Objective Capacitated Vehicle Routing Problem, MOCVRP），本文提出LP-based CFRS启发式算法以高效规划车辆配送路径。该问题的优化目标包含四项：（1）最小化车队总运营成本（即燃油消耗成本与驾驶员超时工作成本）；（2）为与客户保有紧密私人关系的驾驶员分配配送及协助任务；（3）平衡各车辆的配送载荷；（4）降低二氧化碳排放量。研究构建了四类线性规划聚类模型，包含三类独立聚类模型与一类折中解聚类模型，用于将客户划分为不同聚类簇；同时开发了一套线性规划路径规划模型，用于对每个聚类簇内的客户进行排序，以生成一条以配送仓库为起讫点的配送路径。
随后，本文提出DRATP方法，用于为每台车辆精准规划抵达客户处的时间，该方法综合考量道路限制、交通拥堵、带实时交通状况的出行时长以及驾驶员行为等因素。研究提出三类融入驾驶员行为特征的优化技术，以提升到达时间预估的精准度。该DRATP方法支持规划人员与应用软件之间的交互式决策。
基于一项真实案例研究，结果表明所提出的LP-based CFRS启发式算法可高效规划车辆配送路径，能够兼顾四项优化目标，且所需计算时长处于合理范围。但由于该算法采用固定出行时长进行计算，无法提供精准的客户到达时间。另一项真实案例研究结果显示，所提出的DRATP方法可精准确定每台车辆的客户送达时间；相较于未考虑驾驶员行为的DRATP方法，融入驾驶员行为特征的DRATP方法可将到达时间预估准确率提升约50%。