Home | | **Operations Research An Introduction** | | **Resource Management Techniques** | Examples of the Shortest-Route Applications or Problem

The shortest-route problem determines the shortest route between a source and destination in a transportation network. Other situations can be represented by the same model, as illustrated by the following examples.

**SHORTEST-ROUTE PROBLEM**

The
shortest-route problem determines the shortest route between a source and destination
in a transportation network. Other situations can be represented by the same
model, as illustrated by the following examples.

**Examples of the Shortest-Route
Applications **

Example
6.3-1 (Equipment Replacement)

RentCar
is developing a replacement policy for its car fleet for a 4-year planning
horizon. At the start of each year, a decision is made as to whether a car
should be kept in operation or replaced.

A car
must be in service a minimum of 1 year and a maximum of 3 years. TIle following
table provides the replacement cost as a function of the year a car is acquired
and the number of years in operation.

TIle
problem can be formulated as a network in which nodes 1 to 5 represent the
start of years 1 to 5. Arcs from nodel (year 1) can reach only nodes 2,3, and 4
because a car must be in operation between 1 and 3 years. The arcs from the
other nodes can be interpreted similarly. The length of each arc equals the
replacement cost. The solution of the problem is equivalent to find-ing the
shortest route between nodes 1 and 5.

Figure
6.10 shows the resulting network. Using TORA, the shortest route (shown by the
thick path) is 1 -> 3 -> 5. The solution means that a car acquired at the
start of year 1 (node 1) must be replaced after 2 years at the start of year 3
(node 3). The replacement car will then be kept in service until the end of
year 4. The total cost of this replacement policy is $12,500 (= $5400 + $7100).

**Example 6.3-2** **(Most Reliable Route)**

1. Q.
Smart drives daily to work. Having just completed a course in network analysis,
Smart is able to determine the shortest route to work. Unfortunately, the selected
route is heavily patrolled by police, and with all the fines paid for speeding,
the shortest route may not be the best choice. Smart has thus decided to choose
a route that maximizes the probability of *not*
being stopped by police.

The
network in Figure 6.11 shows the possible routes between home and work, and the
associated probabilities of not being stopped on each segment. The probability
of not being

stopped
on a route is the product of the probabilities associated with its segments.
For example, the probability of not receiving a fine on the route 1 -> 3 -> 5 -> 7 is .9 X .3 X .25 = .0675. Smart's objective is to
select the route that *maximizes* the
probability of not being fined.

The
problem can be formulated as a shortest-route model by using a logarithmic
transformation that converts the product probability into the sum of the
logarithms of probabilities that is, if *p _{lk}* =

Mathematically,
the maximization of log *p _{lk}* is equivalent to the
maximization of log

Using
TORA, the shortest route in Figure 6.12 is defined by the nodes 1,3,5, and 7
with a corresponding "length" of 1.1707 (= -log *P _{17}).* Thus, the maximum probability of not being stopped
is

**Example 6.3-3** **(Three-Jug Puzzle)**

An
8-gallon jug is filled with fluid. Given two empty 5- and 3-gallon jugs, we
want to divide the 8 gallons of fluid into two equal parts using the three
jugs. No other measuring devices are allowed. What is the smallest number of
transfers (decantations) needed to achieve this result?

You
probably can guess the solution to this puzzle. Nevertheless, the solution
process can be systematized by representing the problem as a shortest-route
problem.

A node is
defined to represent the amount of fluid in the 8-,5-, and 3-gallon jugs,
respec-tively. This means that the network starts with node (8, 0, 0) and
terminates with the desired

solution
node (4,4,0). A new node is generated from the current node by decanting fluid
from one jug into another.

Figure
6.13 shows different routes that lead from the start node (8,0,0) to the end
node (4, 4, 0). The arc between two successive nodes represents a single
transfer, and hence can be assumed to have a length of 1 unit. The problem thus
reduces to determining the shortest route between node (8,0,0) and node
(4,4,0).

The
optimal solution, given by the bottom path in Figure 6.13, requires 7
transfers.

**PROBLEM SET 6.3A**

*1. Reconstruct the equipment
replacement model of Example 6.3-1, assuming that a car must be kept in service at least
2 years, with a maximum service life of 4 years. The planning horizon is from
the start of year 1 to the end of year 5. The following table provides the
necessary data.

2. Figure
6.14 provides the communication network between two stations, 1 and 7. The
probability that a link in the network will operate without failure is shown on
each arc. Messages are sent from station 1 to station 7, and the objective is
to determine the route.

that will maximize the probability of a
successful transmission. Formulate the situation as a shortest-route model and
determine the optimum solution.

*3. Production Planning. *Directeo
sells an item whose demands over the next 4 months are 100,140,210, and 180
units, respectively. The company can stock just enough supply to meet each
month's demand, or it can overstock to meet the demand for two or more
successive and consecutive months. In the latter case, a holding cost of $1.20
is charged per overstocked unit per month. Directeo estimates the unit purchase
prices for the next 4 months to be $15, $12, $10, and $14, respectively. A
selup cost of $200 is incurred each time a purchase order is placed. The
company wants to develop a purchasing plan that will minimize the total costs
of ordering, purchasing, and holding the item in stock. Formulate the problem
as a shortest-route model, and use TORA to find the optimum solution.

**4. Knapsack Problem. *A hiker
has a 5-ft^{3}* *backpack and
needs to decide on the most valuable items to take on the hiking trip. There
are three items from which to choose. Their volumes are 2, 3, and 4 ft3, and
the hiker estimates their associated values on a scale from oto 100 as 30,50, and 70, respectively.
Express the problem as longest-route network, and find the
optimal solution. *(Hint:* A node in
the network may be defined as *[i,* *v],* where *i* is the item
number considered for packing, and *v*
is the volume remaining immediately before a decision is made on i.)

5. An
old-fashioned electric toaster has two spring-loaded base-hinged doors. The two
doors open outward in opposite directions away from the heating element. A
slice of bread is toasted one side at a time by pushing open one of the doors
with one hand and placing the slice with the other hand. After one side is
toasted, the slice is turned over to get the other side toasted. The goal is to
determine the sequence of operations (placing, toasting, turning, and removing)
needed to toast three slices of bread in the shortest possible time. Formulate
the problem as a shortest-route model, using the following elemental times for
the different operations:

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.