The pickup and delivery problem with synchronized en-route transfers for microtransit planning
2021
Microtransit and other flexible transit fleet services can reduce costs by incorporating transfers. However, transfers are costly to users if they have to get off a vehicle and wait at a stop for another pickup. A mixed integer linear programming model (MILP) is proposed to solve pickup and delivery problems with vehicle-synchronized en-route transfers (PDPSET). The transfer location is determined by the model and can be located at any candidate node in the network rather than a static facility defined in advance. The transfer operation is strictly synchronized between vehicles within a hard time window. A heuristic algorithm is proposed to solve the problem with an acceptable solution in a much shorter computation time than commercial software. Two sets of synthetic numerical experiments are tested: 20 instances based on a 5x5 grid network, and 42 different instances of varying network sizes up to 250x250 grids to test scalability. The results show that adding synchronized en-route transfers in microtransit can further reduce the total cost by 10% on average and maximum savings can reach up to 19.6% in our test instances. The heuristic on average has an optimality gap less than 1.5% while having a fraction of the run time and can scale up to 250x250 grids with run times within 5 minutes. Savings may be achievable by incorporating the en-route transfer strategy into dynamic routing settings.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
36
References
0
Citations
NaN
KQI