The period vehicle routing problem: New heuristics and real-world variants

We develop a heuristic for the period vehicle routing problem that uses an integer program and the record-to-record travel algorithm. Our heuristic produces very high-quality results on standard benchmark instances. We extend our heuristic to handle real-world routing considerations that involve reassigning customers to new routes and balancing the workload among drivers across routes. We demonstrate how these new variants can be used by managers to generate effective routes in practice.

Research highlights► An integer programming-based heuristic is developed for the standard PVRP. ► Two new variants that minimize route disruption and balance routes are considered. ► Our IP-based heuristic generates high-quality results on benchmark instances. ► Our heuristic could be used by managers to develop routes in practice.