OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.
A full list of the topics available in OR-Notes can be found here.
Consider the situation shown below where we have a depot surrounded by a number of customers who are to be supplied from the depot.
The depot manager faces the task of designing routes (such as those shown below) for his delivery vehicles and this problem of route design is known as the vehicle routing or vehicle scheduling problem.
Hence the vehicle routing problem can be defined as the problem of designing routes for delivery vehicles (of known capacities) which are to operate from a single depot to supply a set of customers with known locations and known demands for a certain commodity. Routes for the vehicles are designed to minimise some objective such as the total distance travelled.
This problem is one that has a long history of systematic study, the problem first being considered in an academic paper by Dantzig and Ramser published in the late 1950's.
The problem has attracted a lot of attention in the academic literature for two basic reasons:
In the next section we discuss the vehicle routing problem as encountered in practice.
The vehicle routing problem as encountered in practice involves many restrictions on the routes that delivery vehicles can follow (e.g. a limit on the number of hours that a driver can work) and we consider some of the more common restrictions below. We can classify these restrictions to a certain extent as relating either to the vehicles or to the customers. Note here that in any particular case not all of these restrictions may apply, however in thinking generically about the problem it is useful to list all restrictions that can potentially apply.
In the design of vehicle routes to meet the above requirements there are a number of objectives that could be adopted. Three basic objectives can be distinguished:
The cost of vehicles in the vehicle fleet is often regarded as a fixed cost so that the first objective above corresponds to the minimisation of fixed costs; the second objective above corresponds to the minimisation of the running (or variable) costs; and the third objective above corresponds to the minimisation of total cost (the sum of fixed plus variable cost).
To give you an idea of the size of practical vehicle routing problems a typical depot in the United Kingdom (UK) might supply many hundreds of customers a day (using many vehicles). As an example of this I have worked on a problem with 856 customers and 70 vehicles. This problem arose during a consultancy study carried out in the UK. Below we give the background to this study.
The company involved in this consultancy study was a large mail order/catalogue company which operated by taking orders (either by post or by phone) from the general public in the UK and then delivering the goods ordered to the public in their own home. Goods ordered were supplied either:
A large proportion of deliveries were made by company operated vehicles (from a number of depots) and it was this portion of the company's operation that we examined. For the purposes of our study a single depot in England (with a delivery fleet of some 70 vehicles) was chosen as a target for closer analysis.
At first sight this might seem to be a fairly standard vehicle routing study. However, a difficulty arises at the delivery level (the domestic home), simply put there are too many homes. As can be imagined there are many homes that the company has delivered to in the past (at frequent or infrequent intervals). Attempting to design vehicle routes at the individual home level is undoubtedly counter-productive.
However in the UK, as in many other countries, the country has been divided up into a number of areas, based on alpha-numeric postcodes. For example the postcode for Imperial College is SW7 2AZ. The first section (SW7) of this postcode refers to a particular part of the UK (South Kensington, London), whilst the second section (2AZ) refers to a particular part of South Kensington, London. All homes in the UK have a postcode (though some share the same postcode, e.g. all the homes in a particular section of a street might have the same postcode).
Postcodes are widely used throughout the UK and so, for the purposes of our study, we aggregated homes by postcode, thereby defining a number of postal districts. From historical data, for a particular time of the year, the company could then estimate the number of homes in each postal district requiring delivery and, more importantly, the total workload involved in delivering to these homes.
This leads to a vehicle routing problem where each customer represents a postal district and where we have an estimate of the workload involved in delivering to the customer. As an indication of the size of the problem our target depot had 856 postal districts (customers) requiring delivery on any particular day from the delivery vehicles based at the depot.
Since delivery within a postal district involves visiting homes (different homes on different days) within the postal district it follows that the driver of the delivery vehicle needs to be very familiar with the district. A driver constantly consulting a map, or asking people for directions, obviously does not constitute an effective delivery operation. For this reason the company operated fixed routes, i.e. the same vehicle routes were operated unchanged by the same driver for a given period of time (e.g. by season - spring, summer, autumn, winter).
Hence we have a relatively large, but standard, vehicle routing problem, namely the problem of designing fixed routes. This fixed routes problem has been previously studied in the literature (see here), but not to any great extent.
However a further simplification to the problem was possible. Whilst the company wanted fixed routes, one of their major concerns was that the fixed routes would be able to cope with the peak of business during the period for which the routes were to be fixed and operated. Given the nature of their business, demand between customers (postal districts) was highly correlated. Consequently they specified just a single (peak) day's customer demand data (drawn from the winter (Christmas) season), the objective being to design routes that would be able to accommodate such peak demand.
We are left therefore with a single period routing problem, for which many potential algorithms are available. However there was one key requirement which the company had that was non-standard. This requirement was for the customers on a vehicle route to consist of contiguous (adjacent) postal districts.
Recall here that after aggregation each customer is a postal district, which represents a particular area if plotted on a map. Some districts are next to each other on the map and some are not. Partly because of the issue of the driver being familiar with the district, and partly for historical reasons, the company required routes such that each customer on a route was adjacent (in postal district terms) to the customers next to it on the route. In geographic terms the postal districts making up a vehicle route have to be contiguous.
Below we indicate the data we collected for this consultancy study,
For the company each of the postal districts (customers) was considered as being centred at a (x,y) position, based upon the UK Ordnance Survey National Grid coordinates. This position was calculated by finding the (demand) weighted centre of gravity of the homes in each postal district.
We also need to specify, for each customer, which customers are adjacent to it. Whilst we could have collected this information directly from a map, we found it more effective to initially generate adjacency information using some concepts from computational geometry, specifically the Voronoi diagram and the Delaunay triangulation. This initial adjacency information was then adjusted to represent the actual adjacency situation.
All vehicles were identical and for each inter-customer link (i,j) a time for driving that link was established, as was a time for driving from the depot to each customer. These times were calculated by using a commercial computer-based roadmap of the UK, together with company standards for vehicle speeds on the various categories of roads represented in that roadmap.
Total delivery time was the key capacity constraint here, the physical size of the vehicles, and the amount that they could carry, was not a constraint upon the company's operations.
As mentioned previously the company estimated the workload involved in delivering to each customer from historical data. As each customer represents a postal district this workload has two basic components:
The first component of workload was estimated by solving the travelling salesman problem associated with delivering, from the (demand) weighted centre of gravity, to the homes in the postal district. This was done using a commercial vehicle routing package incorporating a computer-based roadmap of the UK. The second component of workload was estimated using company standards for delivery times.
Overall the results were that the company had the potential to substantially reduce the size of their vehicle fleet (to 64 vehicles) and still maintain customer service.
Anyone interested in the technical details of the heuristic algorithm developed to solve the particular vehicle routing problem thrown up by this study should see J.E.Beasley and N.Christofides, Vehicle routing with a sparse feasibility graph, European Journal of Operational Research, volume 98 (1997) pages 499-511.