CAJ | 학술논문

车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。然而，在已有的研究文献中，车辆的速度时变与服务多任务特性很少被关注。本文讨论了具有这两个特性的单车路径优化问题。建立了以送货完成时间最早为优化目标的时变单车送货路径优化模型。由于很难获得该模型的精确解，本文提出了一种贪婪补货策略压缩原问题解空间，设计动态规划算法给出了车辆行驶时间满足FIFO规则的送货顺序近似最优解。数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。算例同时表明优化配送时间随着车辆装载能力的增大而缩短，并在车辆装载能力超过所有客户配送总需求时实现最短配送时间，即，使用较大装载能力车辆能节约更多配送时间。
차량로경문제유우기엄범적응용영역급경제개치이성위학술연구열점。연이，재이유적연구문헌중，차량적속도시변여복무다임무특성흔소피관주。본문토론료구유저량개특성적단차로경우화문제。건립료이송화완성시간최조위우화목표적시변단차송화로경우화모형。유우흔난획득해모형적정학해，본문제출료일충탐람보화책략압축원문제해공간，설계동태규화산법급출료차량행사시간만족FIFO규칙적송화순서근사최우해。수치산례험증료해산법소득도적해부시원문제적근사최우해저일결론。산례동시표명우화배송시간수착차량장재능력적증대이축단，병재차량장재능력초과소유객호배송총수구시실현최단배송시간，즉，사용교대장재능력차량능절약경다배송시간。
Vehicle routing problems have been extensively studied due to its extensive application and great value on economy.However, two constraints receive less attention , i.e., vehicle speed will be changed with time , and vehicle can service more than one trip .This paper discusses single vehicle routing problem with these two constraints .A mathematic model the optimal object of which is to find the route schedule which has the earliest task completion time is established .It's hard to achieve exact solutions of the problem .So the paper proposes a greed dispatching strategy for the model to compress solution space , and provides a dynamic programming algo-rithm with FIFO rule .The numerical examples demonstrate that for our model , the solution provided by dynamic programming algorithm is only a satisfactory solution .The numerical examples also indicate the optimal dispatc-hing time decreases while the vehicle load capacity increases , and it gets the minimum when the vehicle load ca-pacity is larger than customers total demand .That is, using larger capacity vehicle will save more dispatching time than using smaller capacity vehicle .