Mix fleet vehicle routing problem –

An application of Tabu search in the grocery delivery industry  

 

Management Science Honours Project 2002

 

Devern Burchett

Edward Campion

 

email the authors

Introduction

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.

Options Examined

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 Considerations

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. 

Locations

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 Ckm converts radians to kilometres on the earth’s 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.

Demand data

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 m3) 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.

Vehicles

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.

Mathematical Model

The mathematical model developed for solving this problem aims to supply a set of customers, each with known locations and known requirements for grocery items, by using a set of delivery vehicles of known capacity.  The objective is cost minimisation by the design of routes for the vehicles subject to the following constraints:

§         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.

Construction heuristic

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. 

Search heuristic

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. 

1-interchange mechanism

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 Ri to route Rj, whereas the [0,1] operator shifts a customer from route Rj to route Ri.  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. 

2-consecutive node interchange mechanism

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 Ri and inserted in route Rj, or vice versa.

The [2,1] and [1,2] operators swap two consecutive customers from route Ri with one customer from route Rj.  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 Ri with two consecutive customers from route Rj. 

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.

Data management structure

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%.

Reduced neighbourhood scheme

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.

Current Costs

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. 

Results

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

 

Acknowledgments

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. 

References

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