Preview only show first 10 pages with watermark. For full document please download

Clarke Wright

Clarke and Wright Algorithm Laboratorio di Simulazione e Ottimizzazione L M.Battarra, R.Baldacci, D. Vigo Dipartimento di Elettronica, Informatica e Sistemistica e II Facoltà di Ingegneria Università di Bologna rev 2.0, 5/2007 M.Battarra, R.Baldacci, D. Vigo () Clarke and Wright Algorithm rev 2.0, 5/2007 1 / 24 Outline 1 The input data The output data The Clarke and Wright algorithm The merge concept The algorithm schema Data structure Algorithm: the example Pseudocode Solution Data st

   EMBED

Share

Transcript

  Clarke and Wright Algorithm Laboratorio di Simulazione e Ottimizzazione L M.Battarra, R.Baldacci, D. Vigo Dipartimento di Elettronica, Informatica e SistemisticaeII Facoltà di IngegneriaUniversità di Bologna rev 2.0, 5/2007 M.Battarra, R.Baldacci, D. Vigo ()Clarke and Wright Algorithmrev 2.0, 5/2007 1 / 24  Outline 1 The input data 2 The output data 3 The Clarke and Wright algorithm The merge conceptThe algorithm schemaData structureAlgorithm: the examplePseudocodeSolution Data structureImprovement M.Battarra, R.Baldacci, D. Vigo ()Clarke and Wright Algorithmrev 2.0, 5/2007 2 / 24  The input data Capacitated Vehicle Routing problem (CVRP):Input Data Input Data: n  = 4 customers0 depot d  i  = (0, 5, 13, 12, 8)demandsCost Matrix= { c  i  ,  j  } = (i,j) 0 1 2 3 40 0 2 3 2 21 2 0 2 4 42 3 2 0 4.5 53 2 4 4.5 0 34 2 4 5 3 0 Q = 20 vehicle capacity        1 5 2 13 3 12 4 8 M.Battarra, R.Baldacci, D. Vigo ()Clarke and Wright Algorithmrev 2.0, 5/2007 3 / 24  The output data Capacitated Vehicle Routing problem (CVRP):Output Data Output Data:Solution cost: 14Routes: i) Cost: 7;Demand: 18;#cust: 2;Sequence: 0 1 2 0 ii) Cost: 7;Demand: 20;#cust: 2;Sequence: 0 3 4 0        1 5 2 13 3 12 4 8 222332 M.Battarra, R.Baldacci, D. Vigo ()Clarke and Wright Algorithmrev 2.0, 5/2007 4 / 24