Mix
fleet vehicle routing problem
An application of Tabu search in the
grocery delivery industry
The Mix Fleet Vehicle Routing Problem (MFVRP) is a variation of the well-known Vehicle Routing Problem (VRP). The VRP is characterised by a fixed or variable number of vehicles, common vehicles capacities, and minimisation of the total distance travelled by all vehicles as the objective. The MFVRP generalises the VRP by including a vehicle fleet composition decision, using a number of heterogeneous vehicle types. Each vehicle type is characterised by its capacity, fixed cost and variable travel cost. Each route starts and finishes at the depot and the objective is to minimise the cost of servicing all customers. This cost is found from the sum of all fixed costs, plus the variable cost of the distance travelled by each vehicle.
There has been a considerable amount of research developing good heuristics for solving the MFVRP. This literature includes Golden et al (1984) where the same variable cost was used for all vehicles and an unlimited number of vehicles were allowed. Wassan & Osman (2002) utilised a Tabu search meta-heuristic that generated good solutions to a well-known set of test problems. Salhi & Rand (1987) used a modification of the classic Clarke & Wright (1964) savings heuristic to generate good initial solutions.
This paper looks at the application of some of this research to a MFVRP, involving stochastic customer demand and multiple trips, in the grocery supply industry. By applying a Tabu search heuristic better routes were sought with the aim of reducing the costs of meeting delivery commitments. In particular, we examine the possibility of reducing the number of types of vehicle available and the possible delivery implications of this.
Two South Island regions were studied. In Region A three vehicles, all of different types were utilised. Region B had thirteen vehicles of four different types. One Region A and six Region B vehicles were Instant Service Vans. These vehicles follow a set route each week; carry a base stock and allow orders to be filled from this stock upon arrival at each customer.
Several options were evaluated and analysed in order to present a range of choices. The options for change evaluated were:
1. Shifting customers between days, delivering only once per week and optimising the delivery routes with:
1.1. No changes to the current Instant Service Vans operation
1.2. Optimisation of the Instant Service Vans delivery schedules.
2. Amalgamating Instant Service Van deliveries with other deliveries and changing customers between delivery days with:
2.1. Providing one delivery per week.
2.2. Providing two deliveries per week to those customers who currently receive multiple deliveries (either grocery or Instant Service)
3. Delivering only once per week, on one of the days that a customer currently receives deliveries, and optimising the delivery routes with:
3.1. No changes to the current Instant Service Vans operation
3.2. Optimisation of the Instant Service Vans delivery schedules.
4. Amalgamating Instant Service Van deliveries with other deliveries all deliveries being carried out on one of the days that customers currently receive deliveries, by:
4.1. Providing one delivery per week.
4.2. Providing two deliveries per week to those customers who currently receive multiple deliveries (either grocery or Instant Service)
To compare these options data were taken from the last twelve weeks of the previous financial year and examined. The costs for performing these deliveries in the current manner were calculated. It was intended that we would be able to demonstrate how the deliveries over the twelve-weeks could have been performed more efficiently by generating routes that perform better than those currently in place. However, given that the delivery schedule is dynamically changing the solutions found were only valid for the period studied.
Data were collected for a twelve-week period. These data comprised customer locations in the form of GPS co-ordinates, the types of vehicles available and customer demand patterns.
Customer
locations were collected with a handheld GPS unit. The Euclidean distance between customer locations was calculated
from the well-known aviation formulae of Equation
1.
Equation
1
Aviation
formulae for calculating great circle distance
_{}
_{}
Where C_{km} converts radians to kilometres on the earths surface.
Approximate road distances are calculated from the Euclidean distance using a scale factor. Fifty known road distances within Region B were used to determine this scale factor. A scale factor of 1.16 minimised the errors between the calculated distances and the observed distances.
Because each route is comprised of several customers many of the errors should cancel each other out. Therefore, the larger a route the smaller the absolute error is likely to be.
To build a mathematical model of the system some assumptions and approximations were made. Over 16,000 products are distributed in a wide variety of packaging sizes on trucks with differing loading systems. Therefore, because the heuristic would allow customers to shift between delivery vehicles, it was necessary to find a manner of approximating each customers demand in a homogeneous manner. This would then allow each vehicles capacity to be modelled in a similar manner.
Our examination showed that Budget soft drinks (budget) cartons
were the same size or larger than the other cartons used for repack. These budget cartons (0.0315 m^{3})
were also of a similar size to tobacco cartons. Thus all tobacco and repack cartons were assumed to be this
size. Similarly, orange repack crates
are twice the size of the budget cartons and therefore approximated as two
budget cartons.
Of
the 16,427 bulk products that sizes were available for, only 11.6% were larger
than the budget box repack cartons.
Therefore, 88% of the time the approximation exceeds the actual product
size, as demonstrated in Figure
1. This means
that our formulation will generally overestimated the delivery size leaving
some additional room to help cope with the variability in demand.
Figure
1
Product Sizes
Delivery
quantities for an instant service order range from nothing to about four budget
cartons. Fifty invoices were selected
at random and examined. From these we
estimated the number of budget boxes that each order would fill. We found that these deliveries had a mean of
1.8 budget boxes with a standard deviation of 0.8. Therefore, in amalgamating the Instant Service deliveries with
other deliveries we have increased the appropriate demands by two boxes per
visit.
The capacity of each vehicle type is measured on differing scales. Where two different capacities for the same type of vehicle were given, the lower figure was used in our model thus underestimating capacity. It was intended that our search would allow the movement of customers between vehicles so it was necessary to reflect the capacities of each type of vehicle in the homogeneous measure of boxes. Furthermore, current procedures allow only one customer per cage/pallet; consequently the trucks also had capacities relating to the maximum number of customers that could be included. These homogeneous capacities underestimate real capacity, thus underestimating savings. For example each pallet has a capacity of 40 boxes. Thus, an order of 41 boxes reduces the customer capacity by two; yet in reality the additional box would simply be shrink-wrapped to the top of the pallet.
§ The requirements of each customer must be met
§ The capacity constraints of each vehicle must not be violated
§ The weekly and daily number of trips for each vehicle must not be exceeded
§ Where multiple deliveries to customers are possible these cannot occur on the same day
§ The number of customers allocated to some classes of vehicle cannot exceed a predetermined number
§ The capacity constraints of each type of bulk packaging must not be violated
§ Each vehicle route must start and terminate at the depot
To ensure constraints were satisfied we implemented a number of penalty costs. One-off penalties were applied for exceeding the capacity of a vehicle on a given day these were equivalent to the cost of satisfying the most distant customer with an additional delivery for every occurrence. Exponential penalties were also applied for exceeding the maximum number of weekly/daily routes for each vehicle class. A vehicle fleet composition decision was included to determine the optimal fleet mix.
A solution is a sequence of routes. A 0 (depot node) represents the beginning and end of each single route, while each number in the sequence represents a customer. Included as part of the solution are the vehicle that each route is allocated, and the total number of each class of vehicle.
The solution method involved two phases a construction phase and a search phase. Included, as part of the model, was a data management structure that helped speed up the search process.
We used a modification, proposed by Salhi and Rand (1987), of the saving values heuristic of Clarke & Wright (1964) to generate good initial solutions. Savings were calculated from Equation 2. Where, γ is a saving multiplier and is varied between 0 and 2 in steps of 0.1.
Equation 2 Savings calculation
This construction phase involved generating a savings table. The customer that provided the largest saving was then examined. If the addition of this customer to a route did not violate the capacity constraint the customer was added to the current tour, and the procedure was continued. If the addition of a further customer violated the capacity constraint, a 0 was added to the tour to represent a return to the depot. When all customers had been included in a single route several additional empty routes were added to the end of the sequence. This was because the search may well eliminate routes but fails to add additional routes.
The savings multiplier, γ, was then increased and another series of routes were found. The costs for each sequence of routes found from the construction phase were evaluated over the twelve-week period under examination, and the sequence with the least cost was chosen as the tour to begin the search phase on.
For the Tabu search a neighbourhood scheme based on Wassan & Osman (2002) was used. This neighbourhood included a 1-interchange mechanism and 2-consecutive node interchange mechanism based on eight operators.
The
first two of these operators perform a shift process based on the [1,0] and
[0,1] operators. The [1,0] operator
takes a customer from route R_{i} to route R_{j}, whereas the
[0,1] operator shifts a customer from route R_{j} to route R_{i}. In evaluating the entire neighbourhood, both
these moves are accomplished by rotating the first route to the end of the sequence
upon completion of a series of [1,0] moves.
For instance in Figure 2 the movement last trial move in sequence A is the
final [1,0] movement in a series. After
evaluating this move, the first route in sequence A is moved to the end giving
sequence B. This then allows all [1,0]
and [0,1] moves to be evaluated.
Figure 2 - Sequence
Rotation
The second process is based on a [1, 1] operator and represents a swap of two customers between routes.
This interchange mechanism uses the following
additional operators; [2,0] , [0,2] , [2,1] , [1,2] and [2,2]. The [2,0] and [0,2] operators perform an
insert move similar to the [1,0] and [0,1] operators, with the difference being
two consecutive customers are taken from route R_{i} and inserted in
route R_{j}, or vice versa.
The [2,1] and [1,2] operators swap two consecutive
customers from route R_{i} with one customer from route R_{j}. This operator is demonstrated in Figure 3 where a [2,1] operator results in the evaluation of
sequence B, created by the moves demonstrated.
Figure 3 - [2, 1] interchange operator
Similarly, the [2,2] operator swaps two consecutive customers from
route R_{i} with two consecutive customers from route R_{j}.
In the Tabu search,
all swaps are controlled to ensure that only customers swap from one tour to
another i.e. that the depot nodes remain stationary.
To
increase the speed of the heuristic we developed a data management structure to
keep track of each individual delivery routes distance, demand (in boxes, cages
and pallets), and allocated truck (for the fixed costs). This was accomplished by using a number of
12Χn matrices, where n is the number of individual
routes.
When
a neighbouring solution is generated by one of the neighbourhood moves, only
the two affected routes are recalculated.
For example, if a customer is shifted from the first route to the third
route then the distances, demands and allocated trucks, of the first and third
routes are recalculated for each of the twelve weeks. The relevant locations in the matrices are updated to reflect the
performed move. This enables the cost
of the new sequence to be calculated by simple matrix multiplication. If the cost is lower than the current best
cost, or lower than the best iteration cost and the move is not tabu, then the
sequence is stored as the iterations best sequence. The data management matrices are then refreshed and a different
neighbourhood move is evaluated.
The addition of this data management structure increased the number of iterations per hour by approximately 500%.
In solving for Region A the entire neighbourhood scheme was used. However, for Region B, it was necessary to reduce the neighbourhood scheme to significantly increase the number of iterations performed to eliminate penalty costs. At each iteration only 200 neighbourhood moves were examined with the type of each move being selected at random. This was increased to 800 moves after 500 iterations representing an intensification of the solution space search.
The truck delivery schedule was broken down into daily routes for
each region. These routes were mapped
and their sequence estimated. Each
regions route sequences were joined to represent complete weekly delivery
sequences. The costs for performing
these were then calculated over the twelve-week period under examination. These costs were checked with 12/52 of the
annual costs for the trucks involved and the similarity of these figures helped
verify our calculations.
The results
achieved for both regions are summarised in Table 1.
Table 1 - Summary of Savings Possible
Option |
Region A |
Disruption to customers |
Region B |
Saving (%) |
Saving (%) |
||
1.1 |
32 |
High |
21 |
1.2 Method 1 |
46 |
Very high |
36 |
1.2 Method 2 |
36 |
High |
26 |
1.2 Method 3 |
43 |
High |
27 |
2.1 |
69 |
Very High |
66 |
2.2 |
64 |
High |
53 |
3.1 |
26 |
Medium |
15 |
3.2 Method 1 |
40 |
High |
33 |
3.2 Method 2 |
31 |
Medium |
23 |
3.2 Method 2 |
38 |
Medium |
24 |
4.1 |
57 |
Med-High |
59 |
4.2 |
56 |
Med-Low |
54 |
To Foodstuffs S.I.Ltd we are
extremely grateful for the assistance and facilities provided in the course of
this research.
Many thanks also go to Marc
Brienne, Science Account Manager at Hoare Research
Software Ltd, for the use of an evaluation copy of Matlab software.
1. Williams. E. Aviation Formulary V1.04 http://williams.best.vwh.net/ftp/avsig/gcircle.pdf
Accessed April 11, 2002
2. Clarke, G. & Wright, G.W. (1964). Scheduling of vehicles from a central depot to number of delivery points. Operations Research. 12:568-581
3. Golden, B., Assad, A., Levy, L. & Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research. 1:49-66
4. Salhi, S. & Rand, G.K. (1987). Improvements to vehicle routing heuristics. Journal of the Operational Research Society. 38:293-295
5. Wassan, N.A.
& Osman, I.H. (2002). Tabu search variants
for the mix fleet vehicle routing problem. Journal of the Operational research society. 53:768-782