# Optimal Chaining of Vehicle Plans with Time Windows

arXiv: https://arxiv.org/abs/2401.02873 · HTML: https://mlsanity.com/paper/2401.02873/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 22 references that are in the map.
- First posted on arXiv 5 Jan 2024.

## Builds on (most cited first, 3 of 3)

- [Quantifying the benefits of vehicle pooling with shareability networks](https://mlsanity.com/paper/1310.2963/) (2013)
- [Large-scale Online Ridesharing: The Effect of Assignment Optimality on System Performance](https://mlsanity.com/paper/2305.02209/) (2023)
- [Large-scale Ridesharing DARP Instances Based on Real Travel Demand](https://mlsanity.com/paper/2305.18859/) (2023)

## Abstract (arXiv)

For solving problems from the domain of Mobility-on-Demand (MoD), we often need to connect vehicle plans into plans spanning longer time, a process we call plan chaining. As we show in this work, chaining of the plans can be used to reduce the size of MoD providers' fleet (fleet-sizing problem) but also to reduce the total driven distance by providing high-quality vehicle dispatching solutions in MoD systems. Recently, a solution that uses this principle has been proposed to solve the fleet-sizing problem. The method does not consider the time flexibility of the plans. Instead, plans are fixed in time and cannot be delayed. However, time flexibility is an essential property of all vehicle problems with time windows. This work presents a new plan chaining formulation that considers delays as allowed by the time windows and a solution method for solving it. Moreover, we prove that the proposed plan chaining method is optimal, and we analyze its complexity. Finally, we list some practical applications and perform a demonstration for one of them: a new heuristic vehicle dispatching method for solving the static dial-a-ride problem. The demonstration results show that our proposed method provides a better solution than the two heuristic baselines for the majority of instances that cannot be solved optimally. At the same time, our method does not have the largest computational time requirements compared to the baselines. Therefore, we conclude that the proposed optimal chaining method provides not only theoretically sound results but is also practically applicable.