The Consistent Vehicle Routing Problem considering path consistency in a road network
Autor: | Lucas P. Veelenturf, Pengli Mo, Tom Van Woensel, Yu Yao |
---|---|
Přispěvatelé: | Operations Planning Acc. & Control, EngD Data Science Support, EAISI Mobility, Department of Technology and Operations Management |
Jazyk: | angličtina |
Rok vydání: | 2021 |
Předmět: |
Structure (mathematical logic)
Mathematical optimization Computer science Transportation Branch-price-and-cut algorithm Construct (python library) Management Science and Operations Research Road network VRP Set (abstract data type) Consistency (statistics) Path (graph theory) Vehicle routing problem Consistency Routing (electronic design automation) Layer (object-oriented design) Civil and Structural Engineering |
Zdroj: | Transportation Research. Part B: Methodological, 153, 21-44. Elsevier Transportation Research Part B: Methodological, 153, 21-44. Elsevier Ltd. |
ISSN: | 0191-2615 |
Popis: | This paper investigates a new variant of the consistent vehicle routing problem considering path consistency based on the underlying road network (ConVRP R N ). It is the problem of determining a set of consistent paths for vehicles within a certain period (e.g. a week). We propose a flexible strategy to achieve path consistency, providing a discount for the cost of roads that are traversed every day. The objective is to minimize the total travel costs considering the discount for the paths’ consistent parts. We formulate the problem as a set partitioning model and a general arc-flow model, and then solve the problem by a branch-price-and-cut algorithm. The algorithm is based on a two-layer network, including an underlying road-network graph (lower layer) and a serial of customer-based graphs (upper layer). Furthermore, an innovative aggregation technique is proposed to accelerate the algorithm, which is specifically designed for ConVRP R N . Finally, we construct a road network based on the real road-network structure of West Jordan and demonstrate the effectiveness of our approach on a set of numerical experiments. The impact of consistency discount is also analyzed to provide information and inspiration for tactical decision making. |
Databáze: | OpenAIRE |
Externí odkaz: |