Contributed Session Tue.1.H 0106

Tuesday, 10:30 - 12:00 h, Room: H 0106

Cluster 13: Logistics, traffic, and transportation [...]

Routing with time windows


Chair: Paul Stursberg



Tuesday, 10:30 - 10:55 h, Room: H 0106, Talk 1

Juan Manuel Otero
A hybrid evolutionary approach for solving the vehicle routing problem with time windows (VRPTW)

Coauthor: Erick Lanford


In this paper an evolutionary strategy for solving the VRPTW is proposed. The main idea of this approach is to use routing constructive heuristics for generating the initial population and for designing the genetic operators.
Modifications of the push forward insertion heuristic [2] and of an efficient insertion heuristic proposed by Campbell and Savelsbergh [1] are introduced. Both algorithms are used in an adequate proportion, depending on the number of customers, in order to combine the simplicity of the first and the high performance of the second one.
In order to analyze the behavior of the proposed approach, it was programmed in C#. Computational tests were performed, using ten problems of the Gehring/Homberger library. The results were very similar to the best solutions reported in the literature and, for some problems, the obtained solutions are the best known so far.

  1. A. Campbell, M. Savelsbergh, "Efficient insertion heuristics for vehicle routing and scheduling problems''. Transportation Science Vol. 38, No. 3.
  2. M. Solomon, "Algorithms for the vehicle routing and scheduling problem with time windows constraints''. Operations Research 35, 1987.



Tuesday, 11:00 - 11:25 h, Room: H 0106, Talk 2

Tiago Morais Montanher
An integer programming model for the oil transference in refineries under time window constraints


Programmers of oil refineries often face the problem of moving their commodities between tanks. The transference is made through a shared pipeline network. Each pipeline can take only one transference at time which has costs due to degradation and safety issues. The programmer also needs to consider delivery times at each destination which is usually expressed in terms of a time window. We model this scenario as the problem to find k-vertex disjoint paths in a graph under time window constraints. Here k is the number of transferences. Each edge (pipeline) has a cost and a transfer time depending on the commodity transferred. We ask for independent paths to satisfy time constraints while minimizing total transference costs. Our formulation leads to a branch and price algorithm which combines an integer programming model with a Dantzig Wolfe decomposition reformulation in order to treat time constraints. We show numerical results in a real but simplified plant with 117 equipments, 230 pipelines and a variable number of simultaneous transferences.



Tuesday, 11:30 - 11:55 h, Room: H 0106, Talk 3

Paul Stursberg
Vehicle routing with flexible load carriers

Coauthors: René Brandenberg, Michael Ritter


In many Vehicle Routing applications, using containers allows to shorten loading times and compose (potentially more efficient) tours more flexibly. We examine the optimization problem that occurs in settings, where a small number of containers is used to fulfill transportation tasks on a graph. To derive an ILP model, we consider a graph, where each task is represented by a vertex and arcs correspond to tasks directly succeeding each other. Now, the problem is related to the Vehicle Routing Problem with Time Windows, but constraints added to account for container usage render common decomposition approaches more or less useless.
Instead, we can embed the problem into a broader framework which encompasses applications from routing on a multi-graph to Airline Crew Scheduling. The framework uses of a number of independent transportation layers which passengers can travel on and change between to fulfill certain objectives.
This approach motivates a new model which treats containers as passengers in the described framework, thus circumventing major deficiencies of the original model, significantly decreasing its size and allowing a number of new instances to be solved to optimality


  cash advance online . When the problem is not treated, it can ruin intimate life of couples and destroy their relationships. Viagra Professional was produces not to let this happen. Professional means highly qualified. It strikes the target and doesn't allow a disorder to occupy man's body.