5
O N L I N E T U T O R I A L*
Vehicle Routing and Scheduling
1. (a) Routing problems concern determining the order in
which a single vehicle or several vehicles are to visit de-
livery or pick-up points. The order in which these points
(called nodes) are visited is called a tour, the starting
point of which is called the depot node. The objective is
2. (a) The classic traveling salesman problem (TSP)
involves routing of a single vehicle though a large number
of nodes
at which a pickup or delivery may occur and where the
vehicle does not have a limitation on capacity. No time
arcs of the tour, rather than at the nodes. An example is
trash pick-up or snow removal. As with the TSP the tour
begins and ends at a depot node. In this type of problem,
the nodes (in the TSP sense) are so close together they
cannot be considered discretely, thus it is easier to deal
with
demand on the arcs rather than at the nodes.
(c) In a vehicle routing problem (VRP), there are several
vehicles which travel from a single depot. The vehicles
have varying capacity, and this affects the route in that
a single vehicle can visit a limited number of nodes.
As with the TSP, demand occurs at the nodes. In contrast,
*Source: C. Haksever, B. Render, R. Russell, R. Murdick, Service Manage–
ment and Operations, 2nd ed. (Upper Saddle River NJ: Prentice Hall, 2000).
Copyright ©2014 Pearson Education, Inc.
4. (a) Deadhead time is nonproductive travel time incurred in a
scheduling problem, i.e., the time to travel to a job.
(b) A depot node is the point of origin for a tour. It may be
arbitrarily assigned in most routing problems.
5. (a) A feasible VRP tour means that the sum of the demands
from the nodes assigned for the vehicle does not exceed
the capacity of the vehicle and each node in a vehicle’s
tour is visited only once.
and 1 P.M.
(d) A node precedence relationship means that one node must
be visited before another node. This situation may occur
or b → a is different, the matrix is asymmetric.
Such a situation may arise if there is construction in one
8. Objectives that might be used to evaluate routes and schedules:
(a) School buses: (1) Minimizing travel time to school;
(2) Minimizing cost.
(b) Furniture delivery trucks: (1) Minimizing travel time;
9. (a) Mass transit system: (1) Breakdowns;
(2) Construction;
of distance or dollars) of not connecting two nodes into a partial
tour or route.
T5.1 Assume that node 1 is the depot node.
T5.2 The cost of inserting node 2 between 1 and 3:
(a) I13 = C12 + C32 – C13 = 5 + 6 – 7 = 12
The cost of inserting between 3 and 5:
T5.4 (a) Nearest neighbor heuristic solution with depot node = 1.
Hook-up nodes:
(1) 1–2
2 alternatives.
If we continue with the 7–1 possibility, the hook-ups are:
4–5–7–1–2–3–6–8–4; 39.1 miles
Alternatively, we could have selected 7–6 at branch 3.
The resulting tour would then be:
4–5–7–6–1–2–3–8–4; 39.3 miles
Note that the NNP cannot guarantee the same total tour
length for all tours when multiple solutions are present.
T5.5 The savings matrix generated from the C&W heuristic is
(in miles):
3
4
6
7
8
2
3.9
2.6
1.3
0.8
0.0
3
—
6.6
5.3
2.7
0.2
4
—
6.2
4.0
0.9
5
9.9
6.6
2.6
6
—
8.5
3.6
7
—
3.2
For example, the savings S23 = 22 + 5.8 – 4.1 = 3.9 miles.
Also, Sij = Sji for all i and j.
First, rank the savings from highest to lowest. Move
5–6–7. Skip this link and move to the next feasible link.
(d) Link 3 and 4; (3–4)
(e) Link the Step d subtour with the other subtour (5–6–7)
2–3–4–5–6–7
(g) Link 8 and 7; 2–3–4–5–6–7–8
(h) The tour begins and ends at the depot node, thus the so-
of 27.3 miles. Compare this with the NNP solution in
Problem T5.4, which is 33.9 miles.
T5.6 (a) The NNP for vehicle 1 yields 2 tours: 1–2–4–3–5–1 at
a cost of $134 and 1–3–4–2–5–1 at a cost of $152.
For vehicle 2, three tours are possible:
1–6–9–8–7–10–1 ($204); 1–6–10–9–7–8–1 ($209);
and 1–6–10–9–8–7–1 ($188). When multiple solutions
are present, the lowest cost solution should be selected,
($134 and $188, for vehicles 1 and 2, respectively).
Copyright ©2014 Pearson Education, Inc.
4. (a) Deadhead time is nonproductive travel time incurred in a
scheduling problem, i.e., the time to travel to a job.
(b) A depot node is the point of origin for a tour. It may be
arbitrarily assigned in most routing problems.
5. (a) A feasible VRP tour means that the sum of the demands
from the nodes assigned for the vehicle does not exceed
the capacity of the vehicle and each node in a vehicle’s
tour is visited only once.
and 1 P.M.
(d) A node precedence relationship means that one node must
be visited before another node. This situation may occur
or b → a is different, the matrix is asymmetric.
Such a situation may arise if there is construction in one
8. Objectives that might be used to evaluate routes and schedules:
(a) School buses: (1) Minimizing travel time to school;
(2) Minimizing cost.
(b) Furniture delivery trucks: (1) Minimizing travel time;
9. (a) Mass transit system: (1) Breakdowns;
(2) Construction;
of distance or dollars) of not connecting two nodes into a partial
tour or route.
T5.1 Assume that node 1 is the depot node.
T5.2 The cost of inserting node 2 between 1 and 3:
(a) I13 = C12 + C32 – C13 = 5 + 6 – 7 = 12
The cost of inserting between 3 and 5:
T5.4 (a) Nearest neighbor heuristic solution with depot node = 1.
Hook-up nodes:
(1) 1–2
2 alternatives.
If we continue with the 7–1 possibility, the hook-ups are:
4–5–7–1–2–3–6–8–4; 39.1 miles
Alternatively, we could have selected 7–6 at branch 3.
The resulting tour would then be:
4–5–7–6–1–2–3–8–4; 39.3 miles
Note that the NNP cannot guarantee the same total tour
length for all tours when multiple solutions are present.
T5.5 The savings matrix generated from the C&W heuristic is
(in miles):
3
4
6
7
8
2
3.9
2.6
1.3
0.8
0.0
3
—
6.6
5.3
2.7
0.2
4
—
6.2
4.0
0.9
5
9.9
6.6
2.6
6
—
8.5
3.6
7
—
3.2
For example, the savings S23 = 22 + 5.8 – 4.1 = 3.9 miles.
Also, Sij = Sji for all i and j.
First, rank the savings from highest to lowest. Move
5–6–7. Skip this link and move to the next feasible link.
(d) Link 3 and 4; (3–4)
(e) Link the Step d subtour with the other subtour (5–6–7)
2–3–4–5–6–7
(g) Link 8 and 7; 2–3–4–5–6–7–8
(h) The tour begins and ends at the depot node, thus the so-
of 27.3 miles. Compare this with the NNP solution in
Problem T5.4, which is 33.9 miles.
T5.6 (a) The NNP for vehicle 1 yields 2 tours: 1–2–4–3–5–1 at
a cost of $134 and 1–3–4–2–5–1 at a cost of $152.
For vehicle 2, three tours are possible:
1–6–9–8–7–10–1 ($204); 1–6–10–9–7–8–1 ($209);
and 1–6–10–9–8–7–1 ($188). When multiple solutions
are present, the lowest cost solution should be selected,
($134 and $188, for vehicles 1 and 2, respectively).