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

 

Abstract:
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

 

Abstract:
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

 

Abstract:
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

 

  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis Sale was obtained in Europe, Australia, New Zealand.