节点具有双重需求的车辆路径问题及其性质

王科峰, 叶春明, 唐国春

系统科学与数学 ›› 2011, Vol. 31 ›› Issue (10) : 1185-1196.

PDF(467 KB)
PDF(467 KB)
系统科学与数学 ›› 2011, Vol. 31 ›› Issue (10) : 1185-1196. DOI: 10.12341/jssms11698
论文

节点具有双重需求的车辆路径问题及其性质

    王科峰, 叶春明, 唐国春
作者信息 +

THE VEHICLE ROUTING PROBLEM  AND IT'S PROPERTY WITH NODES HAVING  DOUBLE DEMANDS

    WANG Kefeng, YE Chunming, TANG Guochun
Author information +
文章历史 +

摘要

在原有同时收发车辆路径问题定义的基础上, 将节点需求与车辆容量的关系拓展到允许节点需求大于车辆容量的情形.
接着对集送货需求可拆分车辆路径问题和同时收发车辆路径问题的可简化性进行了研究. 给出了两类问题可简化的定义, 并得到
了当距离满足三角不等式, 车辆容量为1时集送货需求可拆分车辆路径问题可简化并与同时收发车辆路径问题等价, 而当容量大于
等于2时两类问题都不可以简化的结论. 同时也对两类问题当车辆容量等于1时, 以及大于等于3时的计算复杂性给出了证明. 最后
通过一个实例说明了集送货需求可拆分车辆路径问题与同时收发车辆路径问题在最优解的结构性质方面存在着明显差异.

Abstract

Based on the original definition of the Simultaneous Pickup and Delivery Vehicle Routing Problem, the relationship between the
vehicle's capacity and the demand of the node was expanded into the case that the later was permitted to be greater than the former. Then the
reducibility of the Simultaneous Pickup and Delivery Vehicle Routing Problem and the Split Vehicle Routing Problem with Pickup and Delivery
was studied. The reducibility definitions of these two problems were given. It follows  that when the distance   satisfies  the triangle inequality and the vehicle's capacity is equal to 1, the Split Vehicle Routing Problem with Pickup  and Delivery is reducible and equivalent to the Simultaneous Pickup and Delivery Vehicle Routing Problem, and that when the vehicle's capacity is greater than or equal to 2, these two problems were irreducible. Then the complexity of these two problems is proved when the vehicle's capacity was equal to 1 and greater than or equal to 3. Finally an example shows  the obvious structural difference  of the optimal solutions between the Split Vehicle Routing Problem with Pickup and Delivery and the Split Vehicle Routing Problem.

Key words

Supply chain distribution network, simultaneous pickup and delivery vehicle routing problem,  / split vehicle routing problem with pickup and delivery, reducibility, computational complexity.

引用本文

导出引用
王科峰 , 叶春明 , 唐国春. 节点具有双重需求的车辆路径问题及其性质. 系统科学与数学, 2011, 31(10): 1185-1196. https://doi.org/10.12341/jssms11698
WANG Ke-Feng , YE Chun-Ming , TANG Guo-Chun. THE VEHICLE ROUTING PROBLEM  AND IT'S PROPERTY WITH NODES HAVING  DOUBLE DEMANDS. Journal of Systems Science and Mathematical Sciences, 2011, 31(10): 1185-1196 https://doi.org/10.12341/jssms11698
中图分类号: 68Q25    90B20    90C60   
PDF(467 KB)

Accesses

Citation

Detail

段落导航
相关文章

/