Multi-attribute vehicle routing problems

Multi-attribute vehicle routing problems: Exploring the limits of exact methods in practice

van der Sar, Erica (TU Delft Electrical Engineering, Mathematics and Computer Science)

van Iersel, L.J.J. (mentor)
Looije, Daphne (mentor)
Aardal, K.I. (graduation committee)
Nane, G.F. (graduation committee)

Delft University of Technology

Applied Mathematics

2018-03-21

The companies CQM and EVO-it work together to help many different companies with solving their vehicle routing problems. EVO-it provides the interface of the software that the companies can use for route planning and CQM provides the technology that is used to solve the route planning problems, which concerns a lot of mathematical programming. The difficulty of solving these problems is that real-life problems usually deal withmulti-attribute vehicle routing problems, which are problemswith multiple characteristics, such as time windows and vehicle restrictions. These characteristics influence the solving process and the quality of the solution of the method used to solve the problem. Since these attributes can vary a lot per company, it is a difficult task for CQM to provide the best solving method for all problem types. Even though CQM has provided a very complex method that can handle many problems, it is unclear how far from the optimum solution the provided solutions are.
The goal of this project was to investigate the improvement possibilities of the current method used by CQM.
In this thesis many different solving methods for the vehicle routing problem are evaluated and their qualities are discussed. Furthermore, information from the companies that are using the software of EVO-it is collected. With this information an overview of the problem types occurring at these companies is provided. Such an overview had not been made before and will be very useful for CQMand EVO-it to make more problem type specific improvements to the solving method.
Furthermore, this thesis describes two exact methods for solving vehicle routing problems similar to the real-life problems occurring at the clients of EVO-it. One of these methods uses a three-index flow formulation and the other one uses a set partitioning formulation and is based on the method described by Baldacci andMingozzi. It is shown that this latter method can be used to solve instances with up to 40 orders. In addition, both methods can deal with several complicated attributes, including capacity constraints, distance constraints, different type of costs and heterogeneous vehicles. Moreover, it can even deal with instances where not all orders can or need to be scheduled. In such a case, the orders that are not scheduled will get a penalty. To the best of my knowledge, no previous exact method was able to deal with such instances.

Vehicle Routing
Exact algorithm
Exact Method
Set Partitioning
Two-index flow
Three-index flow
heterogeneous vehicles

http://resolver.tudelft.nl/uuid:ec15c141-289b-4a8d-ae76-652bae893ab4

Student theses

master thesis

© 2018 Erica van der Sar