PDPTW-DB: MILP-Based Offline Route Planning for PDPTW with Driver Breaks

Agrima Khanna, Fangqi Liu, Samir Gupta, Sophie Pavia, Ayan Mukhopadhyay, Abhishek Dubey

Proceedings of the 26th International Conference on Distributed Computing and Networking 2025 ICDCN '25

PDF DOI

Why This Matters

Existing vehicle routing formulations often overlook mandatory driver break requirements or handle them as post-hoc constraints, leading to infeasible or inefficient solutions in practice. PDPTW-DB is innovative because it integrates break scheduling directly into the optimization formulation, enabling principled trade-offs between vehicle utilization, travel distance, and driver compliance with service regulations. This bridge between operational planning and human factors considerations addresses a critical real-world constraint.

What We Did

PDPTW-DB presents a mixed-integer linear programming formulation for pickup-delivery problems with time windows that integrates periodic driver break requirements. The work addresses the practical challenge of incorporating mandatory driver rest periods into route planning while maintaining service feasibility. The formulation enables optimization of vehicle routing and break scheduling simultaneously, accounting for realistic constraints like hours-of-service regulations, service time windows, and vehicle capacity limitations.

Key Results

Implementation and evaluation using real Microtransit delivery data demonstrates the formulation produces cost-effective solutions while ensuring full regulatory compliance. Experiments validate both computational efficiency of the mixed-integer approach and the quality of solutions achievable when driver breaks are explicitly modeled.

Full Abstract

Cite This Paper

@inproceedings{khanna2025driverbreaks,
  author = {Khanna, Agrima and Liu, Fangqi and Gupta, Samir and Pavia, Sophie and Mukhopadhyay, Ayan and Dubey, Abhishek},
  booktitle = {Proceedings of the 26th International Conference on Distributed Computing and Networking},
  title = {PDPTW-DB: MILP-Based Offline Route Planning for PDPTW with Driver Breaks},
  year = {2025},
  address = {New York, NY, USA},
  pages = {73--83},
  acceptance = {32},
  publisher = {Association for Computing Machinery},
  series = {ICDCN '25},
  abstract = {The Pickup and Delivery Problem with Time Windows (PDPTW) involves optimizing routes for vehicles to meet pickup and delivery requests within specific time constraints, a challenge commonly faced in logistics and transportation. Microtransit, a flexible and demand-responsive service using smaller vehicles within defined zones, can be effectively modeled as a PDPTW. Yet, the need for driver breaks—a key human constraint—is frequently overlooked in PDPTW solutions, despite being necessary for regulatory compliance. This study presents a novel mixed-integer linear programming formulation for the Pickup and Delivery Problem with Time Windows and Driver Breaks (PDPTW-DB). To the best of our knowledge this formulation is the first to consider mandatory periodic driver breaks within optimized Microtransit routes. The proposed model incorporates regulatory compliant break scheduling directly within the vehicle routing optimization framework. By considering driver break requirements as an integral component of the optimization process, rather than as a post-processing step, the model enables the generation of routes that respect hours of service regulations while minimizing operational costs. This integrated approach facilitates the generation of schedules that are operationally efficient and prioritize driver welfare through driver breaks. We work with a public transit agency from the southern USA, and highlight the specific nuances of driver break optimization, and present a Pickup and Delivery Problem with Time Windows formulation for optimizing Microtransit operations and scheduling driver breaks. We validate our approach using real-world data from the transit agency. Our results validate our formulation in producing cost-effective, and regulation-compliant solutions.},
  category = {other},
  contribution = {lead},
  doi = {10.1145/3700838.3700854},
  isbn = {9798400710629},
  keywords = {vehicle routing, pickup-delivery problems, driver breaks, hours-of-service, mixed-integer programming, logistics optimization, microtransit},
  numpages = {11},
  url = {https://doi.org/10.1145/3700838.3700854}
}
Quick Info
Year 2025
Series ICDCN '25
DOI 10.1145/3700838.3700854
Keywords
vehicle routing pickup-delivery problems driver breaks hours-of-service mixed-integer programming logistics optimization microtransit
Research Areas
transit planning
Search Tags

PDPTW, MILP, Offline, Route, Planning, Driver, Breaks, vehicle routing, pickup-delivery problems, driver breaks, hours-of-service, mixed-integer programming, logistics optimization, microtransit, transit, planning, 2025, Khanna, Liu, Gupta, Pavia, Mukhopadhyay, Dubey, ICDCN25