Special Structures in Vehicle Routing Problems

Lead Research Organisation: University of Warwick
Department Name: Warwick Business School

Abstract

The purpose of this collaborative research is to further develop the theory of polynomially solvable cases for computationally hard problems of combinatorial optimisation; to investigate special structures in real-life vehicle routing applications; and, in collaboration with practitioners from Coventry City Council, to design, implement and test algorithms that would use the identified special structures to find efficient solutions to practical problems.Combinatorial optimisation (CO) is a field of mathematical programming dealing with optimisation problems defined on discrete structures. The applications of CO are varied, including operations management and logistics, computer-aided design and manufacturing, computational biology and linguistics, etc. The Roadmap for Mathematics in European Industry identifies CO as one of the main research priority areas for the scientific community.The vehicle routing problem (VRP) is one of the classical problems of CO. In simple terms, it can be defined as the problem of designing optimal routes for a fleet of vehicles that has to perform a set of transportation tasks. A large number of businesses and public sector agencies have to deal with the VRP on a regular basis. For instance, Coventry City Council, which is a collaborator in this proposal, has a fleet of vehicles performing various transportation tasks, including domestic waste collection, highway gritting, catering (home meals, school deliveries), as well as various passenger transport services. Most CO problems, including the VRP, are quite simple to define but extremely difficult to solve. In theory, such problems are known as NP-hard, and most likely can only be solved by an exhaustive search if an exact optimal solution is required. All known exact algorithms for such problems have super-polynomial time complexity. Despite great efforts, no polynomial-time algorithm has been found for any NP-hard problem, nor has it been proved that such an algorithm does not exist. Given an NP-hard CO problem, one has essentially the following three options:1. to solve small instances of the problem using a super-polynomial exact algorithm;2. to solve special cases of the problem using a specially designed polynomial-time algorithm;3. to solve the problem approximately, using a polynomial-time approximation algorithm, often called a heuristic.Real-life instances of the VRP are usually sufficiently large to rule out option 1. Moreover, they usually contain various additional constraints that would be difficult (or even impossible) to incorporate into the exact procedure and, therefore, some solutions obtained can be in fact infeasible. Polynomially solvable cases required by option 2 are currently known only for some restricted versions of the VRP, in particular for the traveling salesman problem. So, typically, there is little hope that a real-life vehicle routing problem would fit a known special case. For these reasons, option 3 often remains the only choice. Research papers describing heuristics for the VRP are frequently being published in various journals. The reason is in the practical significance on one hand, and in theoretical difficulties of the problem on the other hand. Since the VRP itself is NP-hard, there is not much hope to find an algorithm which would work satisfactorily for a wide range of problems. The approach we are proposing to investigate in this project aims to identify special structures in real-life VRP applications and to use these structures in designing efficient algorithms. We are planning to combine the advances in the investigation of polynomially solvable cases of NP-hard problems with the practice of constructing heuristics for the VRP, and to develop algorithms and prototype software that would efficiently exploit the identified structures to achieve the best possible solutions.

Publications

10 25 50
publication icon
Deineko V (2011) A well-solvable special case of the bounded knapsack problem in Operations Research Letters

publication icon
Deineko V (2009) Fast minimum-weight double-tree shortcutting for metric TSP Is the best one good enough? in ACM Journal of Experimental Algorithmics

publication icon
Deineko V (2009) Fast minimum-weight double-tree shortcutting for metric TSP Is the best one good enough? in ACM Journal of Experimental Algorithmics

publication icon
Deineko V (2009) Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio in Electronic Notes in Discrete Mathematics

publication icon
Deineko V (2011) Unbounded knapsack problems with arithmetic weight sequences in European Journal of Operational Research

publication icon
Çela E (2012) The x-and-y-axes travelling salesman problem in European Journal of Operational Research

 
Description During the work on the project we have developed a novel approach to vehicle routing problems.
We analysed transport services provided by the Coventry City Council and advised how the routing can be improved.
Since then, we keep working on further developments of our approach.
We used our algorithms in international contests on optimisation logistics (Oslo, 2014), Vienna (2015).
We won the third prize in t2015 contest
http://verolog.deis.unibo.it/news-events/general-news/winners-verolog-2015-awards
Exploitation Route We are planning a series of publications (after the efficiency of our approach was confirmed by the successful participation in the international contests). We are planning to apply for a follow up funding to promote a commercial use of the research (currently we are looking for an industrial collaborator)
Sectors Transport

 
Description Together with my MSc students and using the knowledge developed during the work on the project we advised Coventry City Council on possible ways of improving transport services provided by the council.
First Year Of Impact 2011
Sector Transport
Impact Types Policy & public services

 
Description Coventry City Council 
Organisation Coventry City Council
Country United Kingdom 
Sector Charity/Non Profit 
Start Year 2008