Vehicle Routing Problems
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451-0001
The location of a gasoline distribution center (depot) is at (0, 0) in a community laid out in a grid as in Figure 1. From the depot one or more (identical) tanker trucks must depart at the same time to travel to locations which will be referred to as sites. Think of each site as being a gas station. In Table 1 the coordinates of the sites, which are assumed to be reachable via a network grid like streets, are listed. The streets in this urban area are all two way and all block lengths are the same. The amount of gas to be delivered to each site is indicated (in thousands of gallons). Think of this as the weekly demand each gas station has requested for delivery that particular day. The capacity of a tanker truck is 8,000 gallons of gas. Demands for the different sites are to be interpreted in thousands of gallons. We will assume that all of the demand at a single site must be met by one tanker - we are not permitted to have a part of the demand filled by one tanker and part by another tanker.
Table 1: Site locations, and the demand needed at that location:
Site 1: (1, 10); demand 7
Site 2: (3, 8); demand 6
Site 3: (-2, 6); demand 5
Site 4: (5, 13); demand 4
Site 5; (-4, -6); demand 5
Site 6; (-1, 7); demand 4
Site 7; (3, -9) demand 3
Site 8; (5, 5); demand 7
Site 9; (3, 12); demand 2
a. Compute the distance between the depot and all the other sites.
b. Compute the distance between pairs of gas stations.
Comment: What distance does it make sense to use in this situation?
2. If one temporarily disregards the limited capacity of the tankers and one could use a single tanker to make all of the deliveries, what is the shortest route you can find which starts and ends at the depot and visits each gas station once and only once?
3. What is the smallest number of tankers that can be used to carry out the required delivery amounts?
4. Using your answer to #3 as the number of tankers to be used to serve the needs of the gas stations, design routes for each tanker so that the route starts and ends at the depot, and the sum of the distances traveled by the tankers is as small as you are able to find.
5. Design, if you can, a method which does not compute in advance the number of tankers that are required, and which tries to minimize the total distance of the tankers used but does so in a way that fulfills the constraints of the situation.
Things to think about:
1. All of the demands above are less than the capacity of one truck. How might the model be modified for the situation where demand was greater than that one truck?
2. The optimization problem has been set up in terms of the total distance the tankers need to cover. Consider other ways to deal with the problem which would take into account: a. tradeoff between distance and the number of tankers used to meet the demand b. allowing some of the tankers to run two runs on the delivery day if the tradeoff between the costs for the driver and the distances involved warranted. c. Tankers are expensive; one would not have bought as many as one has if there was a reasonable expectation that this number was not required.
3. We have used the taxicab distance between points as a measure of the "cost" of deliveries. What other choices come to mind?
4. Assuming these particular sites all get their deliveries every week, once a week on the same day, how do you think the stations arrive at the amount they request in each delivery?
5. Was the procedure you used "greedy" in some sense, that is, the problem was solved in a series of stages where at each stage you made a "best" choice? If so, can you see how to organize what you did in some other way that it might be "greedy" in some other sense?
6. In the delivery of gasoline presumably it does not matter that the deliveries be made within a particular time window, but if the depot was a newspaper printing plant and the sites were newsstands, it might be that in addition to the demands being met for the different stands, the total time to complete all the deliveries might have to be done within 1.5 hours of the print run for the paper. In this case one might need more trucks than the "minimum" based on truck capacity to get delivery done within the required time window.
7. We saw in #6 that one way in which a gasoline delivery problem might not capture all of the details of other similar types of delivery problems was that some realistic problems require "time delivery windows."
a. List as many delivery problem situations as you can and for each state if the gasoline version captures all of the details needed for use the "algorithm" you developed for solving the gas delivery problem to the "similar" situation.
b. If the new problem situation has features that require you to develop a different procedure to solve than the one you found, can you find a way to modify what you did to deal with your more "complex" problem?
8. What is the lowest grade level that you think it would be meaningful to have a class think about a problem of this sort, perhaps on a smaller scale, say 5 sites rather than 9 sites?
Clarke, G. and J. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964) 568-581.
COMAP, For All Practical Purposes (8th and earlier editions), W. H. Freeman, New York. 2009.
Larson, R. and A. Adoni, Urban Operations Research, Prentice-Hall, Englewood Cliffs, 1981.
Lawler, E. et al. (eds.), The Traveling Salesman Problem, Wiley, New York, 1985.