Solution methods for routing problems

Task

Routing is used when the delivery of small quantities of shipments to many customers has to be organized. The so-called standard problem of routing can be described as follows: Starting from a depot, n customers are to be supplied with goods using a quantity of vehicles with the same loading capacity Q. The demand of each customer as well as the travel times of each customer are determined. The demand of each customer as well as the travel times between the customers and from each customer to the depot or from the depot to each customer are given. Tours are to be executed in such a way that each tour starts and ends at the depot, each customer is served on exactly one tour, and the vehicle capacity Q and a maximum duration D specified for each tour are not exceeded. A set of tours with minimum total duration is sought. In practice, the routing problems to be solved vary considerably. For routing problems such as supplying gas stations with fuel, supplying restaurants with beverages, organizing garbage collection, or collecting milk from farms, additional constraints (different capacities of vehicles, customer time slots, time slots at the depot) or other objective functions (minimizing travel costs or tour durations) must be considered. Classification schemes have been developed in order to describe routing problems and models more easily. Each tour planning problem can be classified with respect to its features and their characteristics.

In a thesis you will deal with a concrete problem from the field of routing. For this purpose, you will be given a scientific article on the problem to be investigated as the starting point for your thesis.

Your tasks include:

  • Describe the problem you are investigating,
  • Classify the problem in the literature,
  • Implement a mathematical model in the optimization software Fico Xpress (the software is provided by the datacenter),
  • Carry out a performance analysis for the implemented model using instances from the literature or instances you have created yourself.

Books:

  • Domschke, W. (2010): Logistik: Rundreisen und Touren, Oldenbourg, München
  • Rieck, J. (2009): Tourenplanung mittelständischer Speditionsunternehmen: Modelle und Methoden, Gabler, Wiesbaden

 

Papers:

  • Butt, S. E., Cavalier, T. M. (1994): A heuristic for the multiple tour maximum collection problem, Computers & Operations Research 21, pp. 101-111
  • Parragh, S. N. et al (2008): A survey on pickup and delivery problems - Part II: Transportation between pickup and delivery locations, Journal für Betriebswirtschaft 58 (2), pp. 81-117

 

For further information, please contact Alexander Beckmann (alexander.beckmann@tu-clausthal.de).