The One Commodity Pickup and Delivery Traveling Salesman Problem with Demand Intervals
The One Commodity Pickup and Delivery Traveling Salesman Problem with Demand Intervals
复制标题
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Güneş Erdoğan;G. Laporte;R. W. Calvo
中科院分区：
文献类型：
--
作者：
Güneş Erdoğan;G. Laporte;R. W. Calvo
研究了具有需求区间的单商品收发货旅行商问题(1-PDTSP-DI)，它是单商品收发货旅行商问题(1-PDTSP)的推广。在1-PDTSP-DI中，要求顶点具有位于给定下界和上界之间的库存，并且初始具有不一定位于这些界限之间的库存。该问题包括使用一辆有能力的车辆在顶点之间重新分配库存，从而满足边界约束并使定位成本最小。这个问题的一个应用出现在共享自行车系统的再平衡操作中。与固定路线相关的重新定位子问题被证明是一个最小费用网络问题。给出了1-PDTSP-DI的两个整数规划公式，以及从其他布线问题的约束中得到的有效的不等式。这些公式中的一种适用于Bders分解方案。给出了两种方法的1-PDTSP算例计算结果。
This study introduces the One-Commodity Pickup and Delivery Traveling Salesman Problem with Demand Intervals (1-PDTSP-DI), a generalization of the One Commodity Pickup and Delivery Traveling Salesman Problem (1-PDTSP). In the 1-PDTSP-DI, the vertices are required to have an inventory lying between given lower and upper bounds and initially have an inventory which does not necessarily lie between these bounds. The problem consists of redistributing the inventory among the vertices, using a single capacitated vehicle, so that the bounding constraints are satisfied and there positioning cost is minimized. An application of this problem arises in rebalancing operations for shared bicycle systems. The repositioning subproblem associated with a fixed route is shown to be a minimum cost network problem. Two integer programming formulations for the 1-PDTSP-DI are presented, together with valid inequalities adapted from constraints derived in the context of other routing problems. One of these formulations is appropriate for a Benders Decomposition scheme. Computational results for instances adapted from the 1-PDTSP are provided for both approaches.