Special Structures in Vehicle Routing Problems

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.