Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
5
O N L I N E T U T O R I A L*
Vehicle Routing and Scheduling
DISCUSSION QUESTIONS
1. (a) Routing problems concern determining the order in
which a single vehicle or several vehicles are to visit de-
salesman problem, and the vehicle routing problem.
(b) Scheduling problems deal with the order in which tasks
objectives may be to minimize cost or idle time.
(c) Combined routing and scheduling problems seek to
2. (a) The classic traveling salesman problem (TSP) involves
routing of a single vehicle though a large number of nodes
the tour, rather than at the nodes. An example is trash
pick-up or snow removal. As with the TSP the tour begins
a single vehicle can visit a limited number of nodes.
a tour must be constructed for all vehicles in the fleet and
capacity for each vehicle is not unlimited, thus capacity
must be considered.
4. (a) Deadhead time is nonproductive travel time incurred in a
scheduling problem, i.e., the time to travel to a job.
5. (a) A feasible VRP tour means that the sum of the demands
from the nodes assigned for the vehicle does not exceed
that the vehicle or server can arrive at a depot (task) with-
in a specified interval. For example, deliveries to a Wash-
6. Both the nearest neighbor procedure (NNP) and Clark &
Wright (C&W) are heuristics for constructing tours for a TSP,
7. Whenever the time or the cost required to move between a → b
380 ONLINE TUTORIAL 5 VEHI CLE RO U TI N G A N D SC H ED U L IN G
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.
should be selected, ($134 and $188, for vehicles 1 and
2, respectively).
T5.7 Using the tours generated by the C&W heuristic,
vehicle 1 has a passenger load of 30;
I51 = $14
The minimum cost is achieved by inserting node 6 between
nodes 5 and 1; the tour would thus be 1–2–4–3–5–6–1 with
CASE STUDY
ited in this problem?
Routing characteristics and one-sided time windows.
2. What type of data would you need to collect in order to
5. Suggest how you would solve the problem if the timed
specimens and routine pickups were considered separately.
Routine pickups could be solved as a multiple TSP; the
