LOCATION-ROUTING PROBLEMS (LRP)
LOCATION-ROUTING FILES
|
Nº |
Customer
File |
Depot
File |
|
1 |
||
|
2 |
||
|
3 |
||
|
4 |
||
|
5 |
||
|
6 |
||
|
7 |
||
|
8 |
||
|
9 |
||
|
10 |
||
|
11 |
||
|
12 |
||
|
13 |
||
|
14 |
||
|
15 |
||
|
16 |
||
|
17 |
||
|
18 |
FILES FORMAT (the same that used by Perl83).
Customer Files: Customer Number, X-coordinate, Y-coordinate, Demand
Depot Files: Depot Number, X-coordinate, Y-coordinate, Capacity, Fixed Cost,
Variable Cost.
FILES INSPIRED IN DATA FROM
Christofides, Nicos, Eilon, Samuel, 1969. An
algorithm for the vehicle-dispatching problem. Operational Research Quarterly 20
(3) 309-318.
Daskin, Mark S.,
1995. Network and discrete location: models, algorithms and applications. John
Wiley & Sons, Inc., New York.
Gaskell, T. J., 1967. Bases for vehicle fleet
scheduling. Operational Research Quarterly 18 (3), 281-295
Min, Hokey, Current, John, Schilling, David, 1992.
The multiple depot vehicle routing problem with backhauling. Journal of Business
logistics, 13 (1) 259-288.
Or, Ilhan, 1976. Traveling
salesman–type combinatorial problems and their relation to the logistics of regional
blood banking. Ph. D. Northwestern University, Evanston, Illinois.
Pearl, Jossef, 1983. A unified
warehouse location-routing analysis. Ph. D. Dissertetion. Northwestern
University, Evanston, Illinois, U SA.
Srivastava, Rajesh, 1986.
Algorithms for solving the location-routing problem. Ph. D. Dissertation, The
Ohio State University.
SOME INSTANCES AND RESULTS
The table shows some results with a Capacitated LRP without Depot Variable
Costs. The vehicle capacity is indicated in the table.
|
Instance |
Veh.
Cap. |
LB |
UB |
Gap(%) |
|||
|
1 |
Christofides69-50x5 |
160 |
549.4 |
|
582.7 |
|
6.06 |
|
2 |
Christofides69-75x10 |
140 |
744.7 |
|
886.3 |
|
19.01 |
|
3 |
Christofides69-100x10 |
200 |
788.6 |
|
889.4 |
|
12.78 |
|
4 |
Daskin95-88x8 |
9000000 |
356.4 |
|
384.9 |
|
8.00 |
|
5 |
Daskin95-150x10 |
8000000 |
43406 |
|
46642.7 |
|
7.46 |
|
6 |
Gaskell67-21x5 |
6000 |
424.9 |
* |
435.9 |
|
2.59 |
|
7 |
Gaskell67-22x5 |
4500 |
585.1 |
* |
591.5 |
|
1.09 |
|
8 |
Gaskell67-29x5 |
4500 |
512.1 |
* |
512.1 |
* |
0.00 |
|
9 |
Gaskell67-32x5 |
8000 |
556.5 |
|
571.7 |
|
2.73 |
|
10 |
Gaskell67-32x5 |
11000 |
504.3 |
* |
511.4 |
|
1.41 |
|
11 |
Gaskell67-36x5 |
250 |
460.4 |
* |
470.7 |
|
2.24 |
|
12 |
Min92-27x5 |
2500 |
3062 |
* |
3062 |
* |
0.00 |
|
13 |
Min92-134x8 |
850 |
|
|
6238 |
|
|
|
14 |
Perl83-12x2 |
140 |
204 |
* |
204 |
* |
0.00 |
|
15 |
Perl83-55x15 |
120 |
1074.8 |
|
1136.2 |
|
5.71 |
|
16 |
Perl83-85x7 |
160 |
1568.1 |
|
1656.9 |
|
5.66 |
|
17 |
Perl83-318x4 |
25000 |
|
|
580680.2 |
|
|
|
18 |
Perl83-318x4 |
8000 |
|
|
747619 |
|
|
|
19 |
Or76-117x14 |
150 |
12048.4 |
|
12474.2 |
|
3.53 |
|
|
* Optimal
solution |
|
Average |
|
|||