The combined manpower-vehicle
routing problem (CMVRP) for multi-staged service: Benchmark Problems
Full paper: B.
Kim, J. Koo and J. Park, "The combined manpower-vehicle routing problem
for multi-staged services," Working Paper,
2008
1. Introduction
The CMVRP deals with multiple specialty teams. Each specialty
team can perform a specific task at customer locations. A customer location
requires a series of staged tasks. Since there are precedence constraints
between the tasks, following tasks cannot be conducted until the prior tasks
are completed. Each staged task should be conducted by an appropriate specialty
team. The teams should be moved by special vehicles because they need special
types of equipment. There are multiple vehicles and the vehicles can move any teams,
but only one team at a time. All the vehicles and the teams start from and end
at the depot. The problems assume that the customer locations require three-stage
tasks.
Figure
1 shows an example problem with five customer locations requiring three tasks,
five special teams, and two available vehicles. Team 1 can perform stage-1
tasks for the customers. Teams 2 and 3 can perform stage-2 tasks. Teams 4 and 5
can do stage-3 tasks. The processing times for stage-1, 2, and 3 at customer C1
are3, 15, and 15 days, respectively. At each customer location, the order of
tasks that should be conducted is stage-1, 2, and then 3. The tasks at a
particular customer location cannot be conducted in parallel.
Figure
1. An example problem
There might be different objectives of the problem
including 1) minimizing total vehicle travel distance, 2) minimizing the make
span, or 3) minimizing the total team waiting time. For our paper, we took the
second objective. Application areas of this problem include construction of
motor ways, construction of oil drilling equipment, and construction of electrical
equipment.
2. Benchmark Problem
Since there are no
publicly available benchmark problems for the CMVRP, several problems were
generated using VRP benchmark problems (Solomon (1987), Golden et al. (1998), and
The VRP Web) and put on http://logistics.postech.ac.kr/CMVRP_benchmark.html
for other researchers. Table 1 shows the characteristics of the problem sets.
The locations of the stops (customers) for the first six problems were
extracted from Solomon (1987)’s benchmark sets and the last four problems were
from Golden et al. (1998). Customer locations have 3 staged tasks with uniformly
distributed processing times. The service time ranges for the tasks were chosen
arbitrarily.
Each problem file has
the data format shown in Table 2. The first column has customer ID, where customer
ID 0 indicates the depot. The second column represents the starting stage of
the customer (all customers have 1 for the column value). The third and fourth
columns represent the customer’s location. The remaining three show the processing
times for the stages. The distance between any two locations is measured by the
Euclidean distance.
Depending on the numbers
of specialty teams for the three stages and the number of vehicles given,
various benchmark problems can be generated. We treated those numbers as
parameters and solved the problems using a limited number of parameter sets as
shown in table 3.
Table 1. CMVRP benchmark problem sets
|
Problem file |
Number of stops |
Service Time1 |
Service Time2 |
Service Time3 |
Geometry source |
|
100 |
U(10,20) |
U(20,30) |
U(20,30) |
R101 of Solomon (1987) |
|
|
100 |
U(10,20) |
U(20,30) |
U(20,30) |
C101 of Solomon (1987) |
|
|
100 |
U(10,20) |
U(20,30) |
U(20,30) |
RC101 of Solomon (1987) |
|
|
100 |
U(100,200) |
U(200,300) |
U(200,300) |
R101 of Solomon (1987) |
|
|
100 |
U(100,200) |
U(200,300) |
U(200,300) |
C101 of Solomon (1987) |
|
|
100 |
U(100,200) |
U(200,300) |
U(200,300) |
RC101 of Solomon (1987) |
|
|
240 |
U(10,20) |
U(20,30) |
U(20,30) |
kelly01 of Golden et al. (1998) |
|
|
480 |
U(10,20) |
U(20,30) |
U(20,30) |
kelly04 of Golden et al. (1998) |
|
|
240 |
U(100,200) |
U(200,300) |
U(200,300) |
kelly01 of Golden et al. (1998) |
|
|
480 |
U(100,200) |
U(200,300) |
U(200,300) |
kelly04 of Golden et al. (1998) |
Table 2. Problem file format
|
Location ID |
Stage |
X COORD. |
Y COORD. |
Service Time1 |
Service Time2 |
Service Time3 |
|
0 |
0 |
35 |
35 |
15 |
29 |
28 |
|
1 |
1 |
41 |
49 |
19 |
27 |
21 |
|
2 |
1 |
35 |
17 |
12 |
28 |
29 |
Table 3. Parameter set
|
Set name |
Number of teams for stage
1 |
Number of teams for stage
2 |
Number of teams for stage
3 |
Number
of vehicles |
|
P1111 |
1 |
1 |
1 |
1 |
|
P1112 |
1 |
1 |
1 |
2 |
|
P1222 |
1 |
2 |
2 |
2 |
|
P1225 |
1 |
2 |
2 |
5 |
|
P2224 |
2 |
2 |
2 |
4 |
|
P2226 |
2 |
2 |
2 |
6 |
|
P2336 |
2 |
3 |
3 |
6 |
|
P3223 |
3 |
2 |
2 |
3 |
|
P3227 |
3 |
2 |
2 |
7 |
|
P3328 |
3 |
3 |
2 |
8 |
References
[1]
Solomon MM. Algorithms for the
vehicle routing and scheduling problem with time window constraints. Operations
Research 1987, 35(2): 254–265.
[2]
Golden BL, Wasil EA,
Kelly JP, Chao IM. The impact of metaheuristics on solving the vehicle routing
problem: algorithms, problem sets, and computational results. In: T.G. Crainic,
and G. Laporte (eds.), Fleet Management and Logistics. Boston: Kluwer Academic
Publishers; 1998. p. 33-56.
[3]
The VRP Web, http://neo.lcc.uma.es/radu-aeb/WebVRP