Page 381 -

MAXIMAL FLOW PROBLEM 361

MANAGEMENT SCIENCE IN ACTION

Delivering frozen food products in Spain
he FRILAC company is based in Pamplona, vehicle fleet size, the capacity of individual vehicles
T Northern Spain and distributes frozen food prod- and the driving time available for each driver. The
ucts throughout the Navarre region by truck. The exist- resulting network had around 50 nodes and 100 arcs
ing approach to scheduling deliveries of products to with the arcs representing roads between delivery
customers was judged to be time-consuming, occa- points. Attached to each arc was information on travel
sionally inaccurate and expensive, so a project was distance and average route speed. The model has
established to look at improving the scheduling. A delivered an estimated 10 per cent cost saving to the
Decision Support System (DSS) was designed to company as well as freeing up staff time, increasing
allow scheduling to identify delivery routes that would productivity and reducing customer complaints.
minimize distance travelled as well as providing
Based on J. Faulin, P. Sarobe and J. Simal, ‘The DSS LOGDIS optimizes
reports for vehicle drivers and estimating route delivery
delivery routes for FRILAC’s frozen products’, Interfaces 35/3 (2005):
costs. However, a number of key constraints had to be 202–214.
incorporated into the model including the existing

Figure 8.19 Maximal Flow Pattern for the Glasgow System Network

3
2 5
7 Maximal flow:
14 000 vehicles
per hour
2
5 3 1 7
7
6 5
1 3 6

3
3

4

NOTES AND COMMENTS

1 The maximal flow problem of this section can 2 Network models can be used to describe a
also be solved with a slightly different formulation variety of management science problems.
if the extra arc between nodes 7 and 1 is not Unfortunately, no one network solution
used. The alternate approach is to maximize algorithm can be used to solve every network
the flow into node 7 (x 57 + x 67 ) and drop the problem. It is important to recognize the
conservation of flow constraints for nodes 1 and specific type of problem being modelled in
7. However, the formulation used in this section is order to select the correct specialized solution
most common in practice. algorithm.

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.