Date: 2009 – 2010
Principal Investigator: Dr Gábor Nagy
Logistics and transport are vital societal functions, pervading all aspects of life. Vehicle routing, the design of the route of vehicles from warehouses or other transport hubs to customers, is a central aspect of logistics systems.
Our project unites, for the first time, two separate strands of vehicle routing research: delivery-and-pickup routing and split routing. The former is applicable to the situation where customers may wish to receive and send goods at the same time (examples of this arise in the postal logistics system and in distribution systems with recycling). The latter allows for the deliveries of customers to be made in more than one visit, thus dividing or “splitting” their loads and has been shown to yield significant reductions in routing costs in some cases. Our business model, the Vehicle Routing Problem with Split Deliveries and Pickups, is appropriate to the situation where customers wish to receive and send goods and are willing to accept vehicles calling on them more than once.
The aims of this project were to develop a model of this problem, to create an appropriate problem-solving tool and to investigate the applicability of this model. In particular, we were interested in establishing the characteristics of real-life delivery-and-pickup problems where splitting loads yields major cost reductions.
Although we designed a mathematical model, that was solvable only for small problems even by powerful software. Hence, the mainstay of our methodology was the development of a heuristic solution algorithm. (Heuristics are tools of artificial intelligence that mimic human reasoning in finding solutions to problems and then making improvements to them.) Our heuristic is an adaptation of a method previously designed by the PI and the CI for the delivery-and-pickup problem.
We carried out extensive empirical testing on academic benchmark instances. In terms of cost reduction, splitting achieved reduction for about a third of the instances, although the savings are generally quite small. However, our experiments also highlighted useful characteristics of the types of customers being split and gave information about the structure of routes containing split customers. This information will be exploited in future research, enabling us to design more efficient solutions algorithms.