Vehicle routing and location problems

The purpose of this seminar is to introduce some important models, algorithms and applications in the fields of vehicle routing and location theory.

A large variety of applications will be described: ambulance location, political districting, design of automated vehicle paths in factories, metro alignmernt location, handicapped people transportation, berth scheduling, satellite mission planning, etc. The course will be complemented by a series of readings and exercises.

Lecture 1: Classical and modern heuristics for the vehicle routing problem

1. General principles

2. Classical heuristics

3. Modern heuristics

Readings:

1. Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., Semet, F. (2002), "A guide to vehicle routing heuristics", Journal of the Operational Research Society 53, 512-522.

2. Cordeau, J.-F., Laporte, G., Mercier, A. (2001), "A unified tabu search heuristic for vehicle routing problems with time windows", Journal of the Operational Research Society 52, 928-936.

Exercises:

Answer fifteen questions on vehicle routing heuristics. (15 points)

Lecture 2: Location models

1. Classical results

2. The p-median problem

3. Ambulance location and relocation problems

Readings:

1. Erkut, E., Myroon, T., Strangway, K. (2000), "TransAlta redesigns its service-delivery network", Interfaces 30(2), 54-69.

2. Gendreau, M., Laporte, G., Semet, F. (1997), "Solving an ambulance location problem by tabu search", Location Science 5, 75-88.

Reading report:

Write a report on one of the two readings. This report must include a summary (15 lines), and a review of the strong and weak points (30 lines).

(25 points)

Exercises:

Answer five questions on location models. (15 points)

Lecture 3: Location applications

1. Political districting

2. Designing automated vehicle paths in factories

3. Metro location

Readings:

1. Bozkaya, B., Erkut, E., Laporte, G. (2003), "A tabu search algorithm and adaptive memory procedure for political districting", European Journal of Operational Research 144, 12-26.

2. Farahani, R. Z., Laporte, G., Sharifyazdi, M. (2003), "A practical exact algorithm for the shortest loop design problem in a block layout", Working paper, GERAD, HEC Montreal.

3. Bruno, G., Gendreau, M., Laporte, G. (2001), "A heuristic for the location of a rapid transit line", Computers & Operations Research 29, 1-12.

Exercises:

Answer five questions on location applications. (15 points)

Lecture 4: Arc routing problems

1. The Chinese postman problem

2. The rural postman problem

3. Advanced arc routing models

Reading:

Ghiani, G., Hertz, A., Laporte, G. (2002), "Recent algorithmic advances for arc routing problems", in Putting Theory into Practice, E. Kozan and A. Ohuchi (eds), Kluwer, Boston, 1-20.

Exercises:

Answer five questions on arc routing problems. (15 points)

Lecture 5: Vericle routing applications

1. The dial-a-ride problem

2. Berth scheduling at the Port of Gioia Tauro (Italy)

3. Maximizing the value of a satellite mission

Readings:

1. Cordeau, J.-F., Laporte, G. (2003),  "A tabu search heuristic for the static multi-vehicle dial-a-ride problem", Transportation Research B 37, 579-594.

2. Cordeau, J.-F.,  Laporte, G., Legato, P., Moccia, L. (2003), "Berth schediling at the Port of Gioia Tauro", Working paper, Centre for research on transportation, Montreal.

3. Cordeau, J.-F., Laporte, G. (2003), "Maximizing the value of a satellite mission", Working paper, Centre for research on transportation, Montreal.

Exercises:

Answer five questions on the course content and readings. (15 points)