东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

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

ISSN号：1000-0577
期刊名称：《系统科学与数学》
时间：0
分类：O224[理学—运筹学与控制论;理学—数学]
作者机构：[1]上海理工大学管理学院,上海200093, [2]河南理工大学能源科学与工程学院,焦作454000, [3]上海第二工业大学管理工程研究所,上海201209
相关基金：国家自然科学基金（20710015,70731160015）,上海市重点学科建设项目（S30504）,高等学校博士点基金（20093120110008）,上海市研究生创新基金（JWCXSL1001）资助项目.

关键词：供应链配送网络, 同时收发车辆路径问题, 集送货需求可拆分车辆路径问题, 可简化性, 计算复杂性., Supply chain distribution network, simultaneous pickup and delivery vehicle routing problem, split vehicle routing problem with pickup and delivery, reducibility, computational complexity.

中文摘要：

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

英文摘要：

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.

同期刊论文项目