Routing Solutions for the Service Industry

Introduction

Vehicle routing problems (VRP) are difficult-to-solve combinatorial optimization problems. At the same time, a VRP addresses an important fact that the distribution costs of many firms in the service industry may account for a major portion of the total logistics costs of the firm. Ever since the problem was introduced by Dantzig and Ramser (1959) over 50 years ago, it has drawn the attention of academic researchers and practitioners due to its attractiveness in theoretical research as well as the potential to apply it in real-world settings.

The goal of the VRP is to determine how to deploy a fleet of vehicles to distribute products or provide services to customers in the most economic way. The cost of such an operation can be a function of different criteria such as time, distance, or service quality. The VRP is a generalization of the well-known traveling salesman problem (TSP), but is more difficult to solve than the same. The VRP is also one of the most widely encountered types of problems in practice; various problems can be modeled as one form of VRP though some problems might not involve transportation of physical goods at all.

The VRP can be extended to a vehicle routing problem with time windows (VRPTW) as time window commitments may be required by customers. Given a fleet of homogeneous vehicles each with a certain capacity, a common depot location where these vehicles start and end their daily operation, and a set of customers with demands for certain products and imposed delivery time windows, the VRPTW attempts to find the most economic way to deliver products to these customers within their required time windows. Each customer is serviced by one and only one vehicle, and each vehicle may have its own working hours defined by a start time and an end time. The total amount of the product loaded on a vehicle cannot exceed the vehicle’s capacity. Finally, at each customer location, the assigned vehicle spends a predefined amount of time to complete the delivery or service.

The VRP has many variants; we, however, focus on VRPTW in this chapter because we find that this version of VRP represents a majority of routing problems found in practice. VRPTW-type problems have many different and interesting versions and they are unarguably one of the most widely studied types of routing problems in the academic literature. Many different models along with exact and heuristic solution techniques have been proposed by scholars, leading to a rich literature on VRPTW.

In public and private service industry, where efficient product pickup/delivery or service person dispatching is sought in order to provide the best service at the lowest possible cost, it is not surprising that the VRPTW is the most suitable model to employ. Note that some industrial applications of VRPTW are indeed another specific version of VRP, which is known as VRP with simultaneous pickup and delivery (VRPPD). In this version, vehicles can have a mixture of pickup and delivery visits to customer sites, such as the case for picking up or delivering cash to ATMs and bank branches. This problem, however, is structurally a different type of problem requiring somewhat different problem solving techniques and hence is considered outside the scope of this chapter.

The service industry nowadays is faced with increased challenges such as offering better services while keeping the overall costs at bay. Higher gasoline and personnel costs put more pressure on providing services efficiently. This economic issues have motivated researchers and practitioners to actively seek the use of state-of-the-art optimization and information technologies. As is the trend in the service industry, it is typically necessary to solve real problems with thousands of customers instead of hundreds, using hundreds of vehicles instead of tens. Furthermore, companies request that VRPTW solutions be more realistic and feasible rather than optimal. In order to provide certain real-time services (e.g. processing a service order over the web), it is required that the solution for a VRPTW be obtained in a matter of seconds, and be as realistic and implementable as it can be. To this end, modern information technologies such as GIS (Geographic Information Systems), GPS (Global Positioning Systems), and/or RFID (radio frequency identification) have been incorporated to solve real-world VRPTW problems.

This chapter has a practice-oriented focus. Instead of an extensive coverage on the theory behind various VRPTW models and their associated solvers, which has been done in numerous papers, we have chosen to focus on existing VRPTW solution reviews and real applications of VRPTW based upon our practical experiences.