Multi-period routing in Hybrid Courier Operations

Multi-period routing in Hybrid Courier Operations

Theodore Athanasopoulos, Ioannis Minis
DOI: 10.4018/978-1-61520-633-9.ch011
(Individual Chapters)
No Current Special Offers


Appointment-based logistics systems, such as special courier services, or repair / maintenance services, face ever increasing competitive pressures for efficiency and on-time performance. For example, in addition to typical (core) operations, courier service providers lately deal with micrologistics activities, such as bulk product deliveries. The promise dates of such deliveries have some flexibility within a pre-specified service level. In this hybrid environment, bulk deliveries are typically planned on an ad hoc basis, without taking explicitly into account the workload for core operations, a practice that may lead to inefficiencies. This chapter proposes a new method to perform assignment of service requests (calls) with some flexibility taking into account expected routes in a multi-period horizon. The problem is solved on a rolling horizon basis in order to address the dynamics of arriving calls. The method is tested through several theoretical examples, as well as in an extensive industrial case, and appears to be superior to current methods used in practice.
Chapter Preview


The problem addressed in this chapter is related to environments in which a fleet of vehicles serves a set of customers using a hybrid service policy that includes (a) mandatory and (b) flexible requests (calls). The mandatory requests must be served strictly within the current period of service (period 1) and the flexible requests must be served within a certain number of subsequent periods (e.g. periods 1, 2, , P).

This is a practical planning problem that may be encountered in many supply chains, and is, at the same time, of significant theoretical interest. In particular, the multi-period nature of the problem has not been given much attention, by the vehicle routing literature. However, addressing this characteristic properly may lead to significant enhancements both in efficiency and service quality. To this effect intelligent computational methods may be used to allocate the flexible service requirements (calls) within the multi-period horizon in a way that minimizes overall routing costs, respecting all service level requirements.

Typical operational environments that feature these characteristics are, among others, courier services as well as on-site (home or other) maintenance and repair services. The courier environment has been the application area of this work. A typical courier network consists of several service centers, which are responsible for the distribution and collection of parcels and letters using a dedicated fleet. The main tasks of a service center can be summarized in (a) deliveries, (b) pickups, and (c) bulk product deliveries. Tasks (a) and (b) are the mandatory tasks, the requests of which arrive usually during the night or early morning prior to the beginning of the service period. Tasks (c) are flexible, arrive daily but should be served within the next P periods (days) after arrival. For these tasks, the customers to be served should be informed at least one period prior to the actual service delivery. A mixture of 80% mandatory calls and 20% flexible calls is typical in many courier operations.

Note that there is no flexibility in planning the “mandatory” calls, since they must be served within the designated period. However, there is flexibility in planning the “flexible” calls, i.e. in selecting the most convenient period within the designated horizon of P periods to serve these calls. A significant issue in allocating the flexible calls, i.e. selecting those to serve during each period of operations, is that their assignment depends on the attributes of the mandatory calls.

Another operational environment of relevance to the service call allocation problem is maintenance/ repair services that are delivered on-site. In this environment, a group of repair persons provide services on location (e.g. appliance, or home equipment, maintenance). Mandatory calls typically are the repair tasks that need immediate attention (e.g. breakdowns), while flexible calls are the ones that concern preventive maintenance. In this case, customer service is typically problematic, forcing customers to wait for unspecified time within the promise day of service delivery. The main reason for this difficulty is that service planners have no prior knowledge of the total picture of the pending tasks, as well as of the dependencies among them (priorities, adjoined requests, etc.). The decisions are mostly based on experience and typically each day is taken as independent from the others, without taking into account the characteristics of the demand.

The overall problem addressed in this chapter falls into the category of vehicle routing problems (VRPs). A comprehensive survey is presented by Toth & Vigo (2002), while the latest advances regarding the most known VRP variations are presented in Golden et al. (2008). Below we focus on the literature related to the two major parts of the problem under consideration: (a) the creation of expected routes and (b) the allocation of flexible service calls. The former part concerns the development of expected (typical) routes the vehicles follow to serve the mandatory calls. These typical routes are used by the second part to allocate the flexible calls throughout the (multiple) periods of the planning horizon (part b).

Complete Chapter List

Search this Book: