固定时间窗快递车辆路径问题建模及求解

Modeling and Solving Express Vehicle Routing Problem with Hard-time Window

研究在给定了分拨中心的网络结构及其服务时间窗口约束和各个分拨中心之间的货物流量结构及其时效约束的情况下,如何安排班车路由以使得班车花费的总成本最小。实际上,此问题是车辆路径问题(VRP)的一个变种。建立问题的数学模型,提出基于贪心启发式方法的快速求解算法,该算法包括三个步骤:第一步为可行货物路由求解(FRA),第二步为货物路由矩阵求解(RSA),第三步为班车安排求解(BSA)。提出的BSA是一种新的班车安排方法:环线班车+单边车,比原有的对称班车安排方法明显提升了班车装载率。还给出评估问题解性能的一个下界模型,可以度量求出解的近似程度。在不同规模的真实数据集上进行计算实验表明,采用新的班车安排算法可以显著降低运输成本。

This paper researches how to schedule cargo and vehicle under the given the network of hubs and their time window plus the goods traffic structure and their time constraint,so that the total cost of vehicles is minimal.Actually,the problem is a variant of vehicle routing problem（VRP）.This paper establishes the mathematical model of the problem,and proposes a fast algorithm based on the greedy heuristic method,which includes three steps：the first step is feasible routing algorithm（FRA）,the second step is cargo routing selection algorithm（RSA）and the third step is bus schedule algorithm（BSA）.BSA is a new bus schedule method：circular car plus unilateral car.With respective to the symmetric bus arrangement method,BSA significantly increases its loading rate.Additionally,the paper gives a lower bound model to evaluate the solution of the problem,which can measure the degree of approximation.The results on different-scaled real data sets show that the new bus schedule method can dramatically reduce the transportation cost.