README.TXT
Santiago Balseiro - 2010


VRPTW Instances (Solomon 1987)
------------------------------

This classic set of problems contains 56 Euclidean instances of
100 clients with time windows but no time dependence. Instances
are grouped into six sets according to their attributes. In sets R1 and
R2 customer coordinates were randomly generated by a uniform
distribution, in sets C1 and C2 they are clustered in groups, and
mixed in problems of type RC1 and RC2. Problem sets R1, C1 and
RC1 have a short scheduling horizon and lower vehicle capacity,
allowing only a few customers to be served by the same vehicle.
Conversely, the sets R2, C2 and RC2 have a long scheduling horizon
and higher vehicle capacity, thus permitting many clients to be
serviced by the same route.

Files:
C1XX.txt - Clustered and short scheduling horizon.
C2XX.txt - Clustered and long scheduling horizon.
R1XX.txt - Random and short scheduling horizon.
R2XX.txt - Random and long scheduling horizon.
RC1XX.txt - Random+clustered and short scheduling horizon.
RC2XX.txt - Random+clustered and long scheduling horizon.


Time Dependent Travel Times (Ichoua et al. 2003)
------------------------------------------------

Ichoua et al. provide a time-dependent extension of
Solomons instances. They divide the scheduling horizon evenly
in three periods: morning rush hour, middle of the day
and evening rush hour. Additionally, arcs are randomly grouped
in three different categories using a 100x100
symmetric category matrix. Each category is assigned a distinct
step speed function, so that category 1 has the lowest speedswhile
category 3 has the highest speeds. All instances use the same
category matrix.

Furthermore, they adjust travel speeds to create 3 different
types of scenarios, called 1, 2, and 3. Scenario 1 is the one with the
lowest time-dependencewhile scenario 3 has the highest degree of
time-dependence. However, they maintain the average speed in
approximately 1, so that the average dif?culty is the same as in
Solomons problems. These three scenarios are applied to every
instance.

Files:
t_dep.dat - Speed matrix for scenerario 1
t_dep2.dat - Speed matrix for scenerario 2
t_dep3.dat  - Speed matrix for scenerario 3
catheg.dat - Cathegory matrix file


Second Category Matrix (Balseiro et al. 2010)
---------------------------------------------

Ichoua et al. present an algorithm for a variant of the
TDVRPTW with soft time windows. When hard time windows are
imposed some instances become infeasible, because it becomes
impossible to service some clients and return to the depot in time.
Unfortunately, we could not ?nd any time-dependent instances
designed for the problem with hard time windows.

In order to test the algorithm in all instances of these authors
and to introduce the least amount of change, we propose a new
categorymatrix. To return feasibility to all instances, the categories
of a few arcs departing from the depot were increased to a higher
level. Hence, after increasing the travel speed of these arcs, all
clients can be served in time again.

For the time periods we divided the day in three equal parts:
 slice 1 = [a_0, a_0 + (b_0 - a_0)/3]
 slice 2 = [a_0 + (b_0 - a_0)/3 , a_0 + (b_0 - a_0)/3*2]
 slice 3 = [a_0 + (b_0 - a_0)/3*2, b_0]
where [a_0,b_0] is the TW of the depot.

Files:
catheg_2.dat - Cathegory matrix file