Open-source VRPLite Package for Vehicle Routing with Pickup and Delivery: A Path Finding Engine for Scheduled Transportation Systems
Open-source VRPLite Package for Vehicle Routing with Pickup and Delivery: A Path Finding Engine for Scheduled Transportation Systems
复制标题
DOI：
10.1007/s40864-018-0083-7
复制
发表时间：
2018-06
影响因子：
1.5
通讯作者：
Xuesong Zhou;L. Tong;M. Mahmoudi;Lijuan Zhuge;Yu Yao;Yongxiang Zhang;Pan Shang;Jiangtao Liu;Tie Shi
中科院分区：
文献类型：
--
作者：
Xuesong Zhou;L. Tong;M. Mahmoudi;Lijuan Zhuge;Yu Yao;Yongxiang Zhang;Pan Shang;Jiangtao Liu;Tie Shi
近年来，自动化、共享化、电动化被视为未来交通领域的“三大革命”，传统的定时公交系统将凭借灵活的服务和自动车辆调度能力而得到极大的增强。许多新兴的定期交通应用包括城市轨道交通的全自动操作系统、高铁的联合线路规划和时刻表以及新兴的自动驾驶车辆调度。车辆路径问题（VRP）有望寻求一组最佳的车辆路线和时刻表以满足客户的需求，并在优化特色调度交通系统的服务方面发挥着至关重要的作用。由于很难找到大规模实例的最佳解决方案，因此大量的研究工作致力于开发有效的算法，而我们的论文提出了基于时间依赖和状态依赖的路径搜索框架的独特视角。本研究开发了一种开源、轻量级的带时间窗口取货和送货（VRPPDTW）建模包，即 VRPLite，为按需运输应用提供高质量和计算高效的解决方案引擎。本文描述了使用超网络表示的 VRPPDTW 时空状态建模过程。该解决方案框架可以嵌入列生成或拉格朗日松弛框架中以处理许多通用应用。给出了许多示例来证明路径搜索算法在各种交通条件和乘客出行要求下的有效性。
Recently, automation, shared use, and electrification are viewed as the “three revolutions” in the future transportation sector, and the traditional scheduled public transit system will be greatly enhanced with flexible services and autonomous vehicle scheduling capabilities. Many emerging scheduled transportation applications include the fully automatic operation system in urban rail transit, joint line planning, and timetabling for high-speed rail as well as emerging self-driving vehicle dispatching. The vehicle routing problem (VRP) holds promise for seeking an optimal set of vehicle routes and schedules to meet customers’ requirements and plays a vital role in optimizing services for feature scheduled transportation systems. Due to the difficulty of finding optimal solutions for large-scale instances, enormous research efforts have been dedicated to developing efficient algorithms, while our paper presents a unique perspective based on a time-dependent and state-dependent path searching framework. An open-source and light-weight VRP with pickup and delivery with time windows (VRPPDTW) modeling package, namely VRPLite, has been developed in this research to provide a high-quality and computationally efficient solution engine for transportation on demand applications. This paper describes the space–time–state modeling process of VRPPDTW using a hyper-network representation. This solution framework can be embedded in a column generation or Lagrangian relaxation framework to handle many general applications. A number of illustrated examples are presented to demonstrate the effectiveness of the path search algorithm under various traffic conditions and passenger travel requirements.