# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**127**> 128 129 130 131 132 133 .. 156 >> Next

Christofides, N.. and S. Eilon (1969). An Algorithm for the Vehicle Dispatching Problem. Opl. Res. Q., 20, 309.

Christofides, N., and S. Korman (1975). A Computational Survey of Methods for the Set Covering Problem. Management Science (Theory), 21, 591.

Christofides, N. (1975). Graph Theory, An algorithmic approach, Academic Press, London.

Christofides N. (1976). The Vehicle Routing Problem. Rev. Frans. Res. Oper., 10, 55.

5 Clarice, G., and J. W. Wright (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Opns. Res., 12, 568.

Dantzig, G. B. and K. H. Ramser (1959). The Truck Dispatching Problem. Opns. Res., 12, 80.

Eilon, S., C. Watson-Gandy, and N. Christofides (1971). Distribution Management, Mathematical modelling and practical analysis, Griffin, London.

Gaskell, T. J. (1967). Bases for Vehicle Fleet Scheduling. Opl. Res. Q., 18, 281.

- IGillett, B. E., and L. R. Miller (1974). A Heuristic Algorithm for the Vehicle Dispatch Problem. Opns. Res., 22, 340.

Gillet, B. E. (1976). Vehicle Dispatching: Sweep Algorithm and Extensions. ORSA-TIMS National Meeting, Miami, 1976.

Golden, B. L. (1975). Vehicle routing problems: Formulations and Heuristic Solution Techniques. ORC Tech. Rep. 113, August, 1975, MIT.

Golden, B. L. (1976). Large-Scale Vehicle Routing and Related Combinatorial Problems, Ph.D. Dissertation, Operations Research Centre, M.I.T., Cambridge, Mass.

Hays, R. (1967). The Delivery Problem. Carnegie Inst, of Tech., Man. Science Res., Report No. 106.

Held, M., and R. Karp (1970). The tsp and Minimum Spanning Trees, I. Opns. Res., 18, 1138.

Held, M., and R. Karp (1971). The tsp and Minimum Spanning Trees, II. Math. Prog., 1, 6.

IBM Corp. (1970). System 360/Vehicle Scheduling Program Application Description-VSPX. Report GH19-2000/0, White Plains, N.Y..

Lin, S., and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the tsp. Opns. Res., 21, 498.

Miller, C., A. W. Tucker, and R. A. Zemlin (1970). Integer Programming Formulation of the Travelling Salesman Problem. J. ACM, 7, 326.

^Mole, R. H. and S. R. Jameson (1976). A Sequential Route-Building Algorithm Employing a Generalised Savings Criterion. Opl. Res. Q., 27, p. 503.

Pierce, J. F. (1970). A two Stage Approach to the Solution of Vehicle Dispatching Problems. Presented at 17th TIMS Int. Conf., London, 1970.

Tillman, F. A. and H. Cochran (1969). A Heuristic Approach for Solving the Delivery Problem. J. Indust. Eng, 19, 354.

CHAPTER 12

Loading Problems

Nicos Christofides Imperial College, London

Aristide Mingozzi Sogesta, Urbino, Italy

Paolo Toth University of Bologna

12.1 Introduction

In this chapter we introduce the class of loading problems, so-called because they arise in situations where items must be loaded into boxes. The well-known knapsack problemconsidered as a problem in its own right in Chapter 9 of this bookis a member of this class. We will, in particular, be considering loading problems in which liquids of different types are loaded into tanks of different capacities. We will be considering both static problems (i.e. ones in which only loading operations of the liquids into the tanks existin which case the order in which the liquids are loaded is immaterial, hence the name static) and dynamic problems (i.e. ones in which both loading of the liquids into tanks and unloading operations of liquids from tanks exist, in which case the order in which operations take place is important). In all cases it is required that different types of liquids must not be mixed in the tanks and some objective must be optimized.

Consider, for example, the loading-only problem with only one liquid (of quantity q) to be loaded into M tanks of capacity Q and value u,, j = 1,..., M. It may be required to load the liquid in such a manner so as to minimize the value of boxes used, i.e. we want to:

M

min z = ?

j = i

M I ~ I

where xi = 1 if tank j is used and 0 otherwise.

340

Nicos Christofides, Aristide Mingozzi, and Paolo Toth

The above problem can be clearly recognized as the knapsack problem. Consider now the dynamic case (also involving only one type of liquid in which an amount qa) must be loaded into the tanks starting at time tm and requiring time At(1), followed by (say) another loading of amount q(2) darting at time f(2) and requiring time Af(2\ followed by (say) a third Dperation of unloading an amount q(3> starting at time t<3) and requiring time lr<3), etc. It may be required to perform these operations using as few tanks is possible (or to minimize the cost of tanks used). These types of problem appear quite often in practical situations. For example, at an oil terminal or Dort, crude oil arrives on ships and is unloaded into storage tanks. In a separate operation batches of crude oil are unloaded from the storage tanks and transmitted via a pipeline network to refineries for conversion into finished products. In the long term a problem exists as to the numbers and sizes of storage tanks that make up the tank farm. However, in the short :erm the tanks are given and what is required is the best method of zonducting the loading and unloading operations.

**127**> 128 129 130 131 132 133 .. 156 >> Next