Periodic vehicle routing problems for customers needing regular deliveries

Posted 27 Apr 2022

ODL Live route optimiser version 1.5.7 and later can solve periodic vehicle routing problems. In periodic problems, customers (e.g. shops needing restocking) need regular repeat deliveries at different frequencies. For each customer, the optimiser algorithm needs to (a) choose its first delivery start date, and (b) assign each delivery to a vehicle and position. The start date locks a customer into a pattern.

This video shows the progress of the ODL Live route optimiser as it solves a periodic problem from one of our test cases. The optimiser is choosing the visit pattern for each customer (e.g. the day of the week they get deliveries) as well as designing efficient daily routes. The deliveries are modelled for a 4-week period. Customers receive deliveries either (a) once only, (b) fortnightly, (c) weekly or (d) biweekly (i.e. twice weekly). A biweekly can be visited either Monday+Thursday, or Tuesday+Friday - so if the first visit is Monday, all later visits are Monday and Thursday. If the first visit for a weekly is Wednesday, all subsequent visits are also on Wednesday. Similarly, if a fortnightly customer is first visited on Friday in the second week, its next delivery will be on the Friday two weeks later.

You can see most of the solution cost improvements are found in the first couple of hundred iterations and by 1000 iterations the optimiser has basically settled. Once the optimiser has settled, the routes form the classic well-separated ‘petal shapes’ which are indicative of an efficient high-quality VRP solution.

Periodic problems can be combined with all of ODL Live’s other modelling features e.g. soft/hard time windows, driver breaks, electric vehicle recharging, quantities, pickup/delivery or many stop jobs, route design/clustering options, on-board time limits, worktime/travel time/travel distance limits and many more.