Continuous approximation for demand balancing in solving large-scale one-commodity pickup and delivery problems
Continuous approximation for demand balancing in solving large-scale one-commodity pickup and delivery problems
复制标题
DOI：
10.1016/j.trb.2018.01.009
复制
发表时间：
2018-03
影响因子：
6.8
通讯作者：
C. Lei;Y. Ouyang
中科院分区：
文献类型：
--
作者：
C. Lei;Y. Ouyang
单商品取货和送货问题（1-PDP）在真实的世界中具有广泛的应用，例如，用于在大城市重新定位自行车，以确保自行车共享系统的可持续运营。然而，解决大规模实例的问题仍然是一个挑战。本文提出了一种混合建模框架1-PDP，连续近似（CA）的方法是用来模拟内部的皮卡和交付路线内的每个多个子区域，而这些子区域的商品的净盈余或赤字的匹配是在一个离散的模型与减少问题的大小。该模型同时考虑了相互依赖的局部路由选择和系统级匹配决策，并提出了一种基于拉格朗日松弛的混合模型求解算法。一系列的数值实验表明，该混合模型能够在较短的计算时间内产生一个很好的解决方案，为大规模的实例。
The one-commodity pickup and delivery problem (1-PDP) has a wide range of applications in the real world, e.g., for repositioning bikes in large cities to guarantee the sustainable operations of bike-sharing systems. It remains a challenge, however, to solve the problem for large-scale instances. This paper proposes a hybrid modeling framework for 1-PDP, where a continuum approximation (CA) approach is used to model internal pickup and delivery routing within each of multiple subregions, while matching of net surplus or deficit of the commodity out of these subregions is addressed in a discrete model with a reduced problem size. The interdependent local routing and system-level matching decisions are made simultaneously, and a Lagrangian relaxation based algorithm is developed to solve the hybrid model. A series of numerical experiments are conducted to show that the hybrid model is able to produce a good solution for large-scale instances in a short computation time.