Optimizing the routing of vehicles

A large proportion of freight distribution is carried out by road vehicles. Assigning customers to the vehicles, followed by routing and scheduling them, involves a set of decisions that can have a significant impact on the costs and levels of service provided. The problem of organizing and routing a fleet in such a way is called the vehicle routing and scheduling problem (VRSP). Where the set of customers and their demands change little, experience can lead to good sets of routes that meet constraints concerning the vehicles, such as their capacities and service requirements (for example time windows for deliveries at customers), and that are close to minimizing the economic costs of the operation. However, when the customer base and demands are changing, it is often advantageous to make use of a computer to solve the problem. A variety of VRSP software packages are available that will provide routes and schedules. It has been suggested that ‘the use of computerized procedures for the distribution process planning produces substantial savings (generally from 5 per cent to 20 per cent) in the global transportation costs’ (Toth and Vigo, 2001).

Reduction in costs comes partly from a reduction in unnecessary distance travelled by making use of better routes, which in itself can lead to a reduction in fuel consumption and hence a reduction in greenhouse gas emissions. However there are additional factors to be taken into account when aiming to reduce the environmental impact of a fleet of vehicles. Not only must each journey be driven in an efficient manner using the most appropriate route, but work items should be ordered in such a way that difficult journeys (for example, into a congested city centre) are scheduled for a time of day where their impact will be minimized.

Reducing commercial vehicle emissions is a key concern on the green logistics agenda. Commercial vehicles account for 22 per cent of CO2 emissions in the UK. Many companies are looking at this area to help reduce their carbon footprint and improve their green credentials. Walmart is aiming to make its vehicle fleet 25 per cent more efficient within three years and 50 per cent in 10 years (Walmart, 2008). In the UK, supermarket chains Tesco and J Sainsbury intend to reduce transport emissions for a case of goods by 50 per cent in five years and 5 per cent in three years respectively (Tesco, 2008; J Sainsbury, 2008).

The aims of this chapter are to define the VRSP in its basic form, introduce some of the sub-problems that arise when considering real world features of VRSPs and discuss some of the issues relating to reducing emissions when solving VRSPs.

Vehicle routing problems

The basic capacitated vehicle routing problem (CVRP) consists of a set of customer deliveries to be made by a vehicle fleet based at a central depot. The travelling distances between each pair of customers as well as to and from the depot are known, each delivery item is of a known amount and each vehicle has a fixed capacity. The aim of the problem is to minimize the total distance driven by the vehicles while satisfying all of the customer orders. Further problem objectives can also be considered, such as minimizing the fleet size or balancing the set of vehicle routes to make them as equal in length as possible.

The problem was first introduced by Danzig and Ramser (1959) and it has received considerable attention since. An overview of the work into the VRSP can be found in books by Golden and Assad (1988), Toth and Vigo (2001) and, more recently, Golden, Reghavan and Wasil (2008). The VRSP is classified as an NP-hard problem, which implies that as the problem size increases, the computation time required to find the optimum solution for any known method increases exponentially. Optimum solutions can be found for problems of limited size; however, in order to find an optimum solution an impractical amount of computation effort can be required to discount all non-optimal routes. In practice heuristic methods are usually applied. Heuristics are not guaranteed to find the optimum solution; however, a well-designed heuristic will find good quality solutions in a reasonable computation time.

There are many commercial software packages available to provide solutions to real-world VRSPs. Such packages offer significant advantages over any manual method through the use of heuristics. Software vendors are keen to publicize the significant sums of money that such an approach can save. However, most are only concerned with maximizing the economic savings, which are usually achieved through minimizing the total travel cost measured from the distance travelled or time taken and minimizing the fleet size. Such improvements will, inevitably, reduce the emissions produced by vehicles; however, none currently aim to minimize the environmental impact directly. OR/MS Today regularly publishes surveys of available packages. In the most recent survey only one software vendor highlighted environmental impact as a future feature/concern for its software package (OR/MS Today, 2008).

Types of problem

The basic CVRP has been introduced in the previous section; however, routing problems are rarely so straightforward in practice. For example, additional constraints that can have a major impact on the operation include legal requirements on driving and working times, and the fact that certain customers require delivery by particular vehicles (for loading and unloading reasons). This section introduces some more of the problem features that can occur in practice, and some of the research into the resulting models.

A very common constraint concerns when a delivery can be made. The time window for a delivery is defined by a start and an end time. Depending on the problem considered, the time window may be treated as either a hard or soft constraint. A hard constraint requires that a vehicle must wait until the time window begins before making a delivery or must not arrive until the time window begins. Once the time window ends the delivery cannot be made. A soft constraint allows the delivery to be made outside of the time window at a penalty cost. This cost can either be a fixed cost or can be proportional to the earliness or lateness of the delivery. Algorithms to find the exact solution to the problem with hard time windows have been developed by Kolen, Kan and Trienekens (1987) and Kallehauge, Larsen and Madsen (2006). Heuristic methods have been used by Bräysy (2002) and more recently by Lau, Sim and Teo (2003) and Fu, Eglese and Li (2008) who consider both hard and soft time windows.

Backhauls

Problems that allow backhauls include customers who require an item be collected and delivered to the depot. This is in addition to the customers expecting deliveries (also referred to as linehauls). It is common that any deliveries are made before backhauls are considered. Approaches giving exact solutions to problems of limited size have been developed, for example by Toth and Vigo (1997) or Mingozzi, Giorgi and Baldacci (1999). Heuristic methods have also been applied to the problem, see Duhamel, Potvin and Rousseau (1997), Brandão (2006) and Tavakkoli-Moghaddam, Saremi and Ziaee (2006).

Pick-up and delivery

In this case each item is picked up from one location and delivered to another (neither of which is the depot). Obviously, each pair (pick-up and delivery) must be assigned to the same vehicle and the pick-up must occur before the delivery. Again, there is a limit on the capacity of the vehicle at any one time. Berbeglia et al (2007) review a wide variety of such problems, including the dial-a-ride problem (DARP), which concerns itself with the transportation requests of bus passengers (usually the elderly or disabled). The DARP can include restrictions on the time between pick-up and delivery, which are more relevant to passenger transport. Cordeau and Laporte (2003) have devised a heuristic approach to the DARP and Wassan, Nagy and Ahmadi (2008) have tackled the more general pick-up and delivery problem.

A problem that is related to both the VRP with backhauls and the VRP with pick-up and delivery is the problem with simultaneous pick-up and delivery. In this case, items are delivered to a customer from the depot and, as the delivery is made, other items are returned to the depot. Originally introduced by Min (1989) to model the movement of library stock, a heuristic approach has recently been developed by Montané and Galvão (2006).

The vehicle fleet is often made up of different types of vehicles with different characteristics, which may be critical when determining vehicle routes. The vehicles used may have different capacities, and this may affect how they are used. In addition, some items may only be delivered by certain vehicles either due to restrictions at the customer location (the site-dependent VRP) or the nature of the item (eg heavy or hazardous items). Nag, Golden and Assad (1988) were among the first to consider such restrictions and implement a heuristic that solves the problem by way of a three-stage process, assigning vehicles to deliveries before attempting to create vehicle routes. A more recent heuristic approach has been presented by Chao, Golden and Wasil (1999).

Open VRSP

The ‘open VRSP’ introduces the idea that routes need not start or end at a depot. This may better reflect the cost structure when distribution is assigned to a third-party logistics provider and the vehicle does not need to return to the depot after the last delivery, but is allowed to go elsewhere to undertake other jobs. Brandão (2004) considers this problem and discusses the subtle differences that occur when not routing to and from a central location. An exact approach to the open VRSP can be found in Letchford, Lysgaard and Eglese (2007).

Dynamic VRSP

The ‘dynamic VRSP’ allows the rescheduling of customer requests once some new information is known. This is different from the standard approach where all information is known and fixed schedules are generated at the start of the day. This new information can be in the form of new customer requests or information regarding possible travel delays. Scheduling new customer requests is the most common dynamic feature and has been tackled by, among others, Gendreau et al (1999) and more recently Ichoua, Gendreau and Potvin (2006). Papastavrou (1996) investigates the problem where there is no initial set of customers at the start of the day and all demands occur dynamically. The heuristics developed take into account traffic density, which would in practice allow the consideration of travel delay information. Taniguchi and Shimamoto (2004) consider dynamic routing to avoid congestion and apply their heuristic to a real-world problem with successful results.

Although there have been technical advances in being able to modify routes according to real-time demands and traffic conditions, there are limits to the benefits that can be achieved in practice. For example, if the logistics operation is concerned with distributing specific orders from a central depot to a set of customers, then the decision about which customers can be serviced on which route must be taken initially when the vehicles are loaded and cannot be subsequently changed, even if traffic conditions change in such a way that a different allocation of orders would have produced better routes.

Stochastic VRSP

In stochastic VRSPs, uncertainties in the demands or travel times are explicitly modelled. A stochastic demand model may be appropriate when the vehicles deliver a resource and the amount required by each customer is not known until the customer is visited. Using an estimate of the demand for each customer, an initial set of routes can be defined. However, should a customer require more of the resource than the vehicle contains, the vehicle will need to return to the depot to get more stock before it can satisfy the customer demand. Each time a delivery is made, a decision must be taken on whether to deviate from the planned route to either visit an alternative customer or return to the depot. Approaches to this problem are given in Yang, Mathur and Ballou (2000) and Secomandi (2001).

Travel times may also be treated as uncertain and modelled according to a probability distribution. Fu (2002) considers stochastic travel times for the dial-a-ride problem. A minimum service rate is defined on the maximum time between pick-up and drop-off for each passenger. A heuristic is used to produce a schedule that, on average, will satisfy this service rate. A different approach is taken by Ando and Taniguchi (2006), where a penalty cost is used to try to eliminate probable delays.

Arc routing problems

The problems discussed so far require serving customers located at specific locations on a road network. Arc routing problems arise when a set of roads have to be visited to provide a service or treatment. Practical examples of services are postal delivery or refuse collection. Examples of treatments are snow ploughing or winter gritting, when salt or some other substance is spread on the roads to prevent ice forming. Similar constraints may need to be considered as for the VSRP, such as the capacity of the vehicles used and any time constraints on the operation. Practical details need to be clear in the modelling, such as whether a vehicle can deliver the service or treatment to a road by travelling down it once in either direction (as is sometimes the case for refuse collection in suburban streets) or whether the vehicle needs to travel down the road twice, once in each direction (as is usually the case where a road has been divided into a dual carriageway). Algorithms and software have been developed for arc routing and take advantage of the different structure of the problem to the VRSP counterpart. Overviews can be found in Wøhlk (2008) and Dror (2000).