Topics in transportation and cargo loading 052013/426

Course description

Teachers

Lectures

Exercises

• [2/9] In home work set [ex2] exercise 2 is the most important.
• [5/9] The lecture tuesday 6/9 has been cancelled.
• [6/9] Please note "Datalogisk kollokvium" friday 9/9.
• [15/9] [ex5] have been updated (an error has been fixed).
• [19/9] Solution to [ex4] put on the web.

Final project

• [3/11] Endnu en lille opdatering, så der ikke bliver genereret cuts og vars samtidig når 2-path cuts findes. Lav "svn up" tak.
• [2/11] En lille opdatering af koden, hvis nogen har haft problemer med at separerer cuts på infeasible løsningerne. Lav "svn up" tak.
• [1/11] Der findes kliker i r102.sol med 25 kunder.
• [1/11] 2-path cut initialiseres med CG_cut_graph(n), hvor n er antal kunder. Brug cut->set_edge(i,j,1) til at give kanter (i,j) koefficient 1 i cuttet. 3-kunde kliker initialiseres med CG_cut_graph(n,2). Brug cut->set_node(i,1) til at sætte kunderne i kliken.
• [27/10] Simon afholder spørgetime til opgaven tirsdag d. 1/11 fra kl. 11 i N037. Send evt. spørgsmål på forhånd.
• [26/10] Venligst lav en "svn up". Jeg har opdateret nogle fejl omkring klikerne. Bemærk at 2-path cuts skrives som et cut af kanter fra den originale formulering. I klikerne noteres de tre kunder med en koefficient på 1. Hvis man har besvær med at få fat i mit katalog, lav en "ls ~spooren" til at starte med.
• [26/10] Bemærk at alle kantvægte er skaleret med 10 for at regne i heltal.
• [19/10] Så skulle SVN virke på både kand- og app-maskiner + brok/tyr/ask.
• [18/10] Der ændret en anelse i opgaven omkring udtjekning af kode. Bemærk at udtjekningen/opdatering kun fungere på app-maksiner + brok/tyr/ask. EDB afdelingnen er ved at opdatere SVN på kand-maskinerne, så forhåbentligt fungere det også snart der.
• [15/10] Der er lidt problemer med den fine udtjekning af koden. Der arbejdes på sagen med god hjælp fra Adam.
  Indtil da kan den kopieres fra "~spooren/studie/topics426"
• [15/10] Konkurrencen gælder kun instanser kørt med 100 kunder.

Plan

Literature

• [1] P.Toth and D.Vigo, An overview of Vehicle Routing Problems, chapter 1 in "The Vehicle Routing Problem" (P. Toth, D. Vigo ed.), 2002.
• [2] G.Laporte, F.Semet, Classical Heuristics for the Capacitated VRP, chapter 5 in "The Vehicle Routing Problem" (P. Toth, D. Vigo ed.), 2002.
• [3] D.S.Johnson, L.A. McGeoch The traveling salesman problem: A case study in local optimization link
• [4] a) J.-F. Cordeau, G. Laporte, A. Mercier, A Unified Tabu Search for Vehicle Routing Problems with Time Windows, Journal of the Operational Research Society 52, 928-936.
  b) C. Prins, A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31 (2004) 1985-2002, link (works from within DIKU)
  c) S. Ropke, D. Pisinger, An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows, to appear in Transportation Science. link
  Supplementary:
  d) D. Pisinger, S. Ropke, A general heuristic for vehicle routing problems, to appear in Computers & Operations Research. link
• [5] a) Bard, J.F. and Kontoravdis, G. and Yu, G., "A Branch and Cut Procedure for the Vehicle Routing Problem with Time Windows", Transportation Science 36 (2), pp. 250 - 269, 2002 link
  b) G.Laporte, F.Semet, Classical Heuristics for the Capacitated VRP, chapter 3 in "The Vehicle Routing Problem" (P. Toth, D. Vigo ed.), 2002.
  c) J. Lysgaard, A. Letchford, R. Eglese, "A new branch-and-cut algorithm for the capacitated vehicle routing problem", Math. Programming, Ser. A 100, pp. 423-445, 2004 link
• [6] a) D.Feillet, P.Dejax, M.Gendreau, and C.Gueguen. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Technical report, Montr'eal:Centre de recherche sur les transports, Universit'e de Montr'eal, Quebec, Canada, 2000. link
  b) S. Irnich and D. Villeneuve. The shortest path problem with resource constraints and k-cycle elimination for k >= 3. Technical report,Les Cahiers du GERAD, HEC Montr'eal, Quebec, Canada, 2003. link
• [7] a) Note
  b) G.Righini and M.Salani. Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Elsevier Science (submitted), 2004.
• [8] Note
• [9]
• [10] a) Dyckhoff "A typology of cutting and packing problems" (udleveres ved forelæsning)
  b) Lodi, Martello, Vigo "Two-dimensional packing problems - a survey" link (works from DIKU)
• [11] a) S.P. Fekete, J.Schepers. "On more dimensional packing I: Modeling" link
  b) D. Pisinger, M.Sigurd. link (works form DIKU)
  c) Supplementary literature: link link link
• [12] Murata et al. "VLSI Module Placement Based on Rectangle-Packing by the Sequence-Pair", IEEE Transactions on CAD of Integrated Circuits and Systems, VOL 15 (12), 1996 link, D. Pisinger "Heuristics for the Container Loading Problem", European Journal of Operational Research 141 (2002) 382--392 link (works from DIKU), Færø et al. "Guided local search fot the Three-Dimensional Bin-Packing Problem", INFORMS Journal on Computing volume 15 (3), 267--283 (2003) link (works from DIKU)
• [13] Egeblad et al. "Fast Neighborhood Search for Two- and Three-Dimensional Nesting Problems", (submitted -- Ask Jens for a copy), Gomes and Oliveira, "A 2-Exchange Heuristic for Nesting Problems", European Journal of Operations Research 141 (2002) 359--370 link (virker fra DIKU)
• [14] M. Gendreau, M. Iori, G. Laporte, S. Martello "A Tabu Search heuristic for the vehicle routing problem with two-dimensional loading constraints"

• [ex1] VRP with time windows (to be handed in tuesday 6/9)
• [ex2] Polynomial heuristics (to be handed in tuesday 6/9)
• [ex3]
• [ex4] Contact Stefan Røpke for a copy of the exercises. Løsning
• [ex5] Exact methods for VRP (Der var en fejl i den oprindelige opgave, dette er en opdateret udgave)
• [ex6] See exercises at the end of the slides.
• [ex7] Exercise (Bidirectional), Exercise (Branch-cut)
• [ex8] Exercise
• [ex9]
• [ex10] Exercise
• [ex11] Exercise
• [ex12] Exercise
• [ex13] Exercise
• [ex14]