Territory Design for the Multi-Period Vehicle Routing Problem with Time Windows

Highlights

• Territory design for multiperiod vehicle routing problem with time windows.

• Contiguous and compact territories for last-mile logistics.

• Real-world case of a distribution system at a major Chilean food company.

• MILP and ad-hoc heuristic for territory design problem for feasible daily routing.

• Methodology for dynamic daily routing based on territories computed for past demand.

Abstract

This study introduces the Territory Design for the Multi-Period Vehicle Routing Problem with Time Windows (TD-MPVRPTW) problem, motivated by a real-world application at a food company’s distribution center. This problem deals with the design of contiguous and compact territories for delivery of orders from a depot to a set of customers, with time windows, over a multi-period planning horizon. Customers and their demands vary over time. The problem is modeled as a mixed-integer linear program (MILP) and solved by a proposed heuristic. The heuristic solutions are compared with the proposed MILP solutions on a set of small artificial instances and the food company’s solutions on a set of real-world instances. Computational results show that the proposed algorithm can yield high-quality solutions within moderate running times. A methodology is proposed in which the territories computed by the proposed heuristic on the past demand of one month are used for the operational routing during the following month, in which the demand is known only one day in advance. An evaluation shows that the territories obtained with our methodology would have led to levels of service significantly better than the ones that were experienced by the company, using a significantly lower number of vehicles to execute the deliveries.

Introduction

Territory Design (TD) problems (Ríos-Mercado, 2020) consist in grouping small geographic areas, called basic units, into larger zones, called territories, which must meet a set of planning criteria depending on the specific application context. Planning criteria most often used correspond to balance, contiguity, and compactness of territories. The balance criterion consists in designing territories of equitable size. The contiguity or connectivity criterion ensures that it is possible to move between any pair of basic units within one territory without crossing any other. And the criterion of compactness corresponds to designing geographically compact territories, i.e., with a dense structure of basic units closely packed together. The contiguity and compactness criteria are widely used in Territory Design because they generally reduce distances and travel times within a territory. For example, when designing territories for a company’s distribution system, such a reduction directly benefits the company’s operational costs. The balance criterion is also quite common. It is related to fairness, for example, with respect to the drivers that execute the deliveries in a distribution system.

This paper is concerned with using a TD-driven methodology to solve a particular last-mile logistics problem. Last-mile logistics represents the last stage of a supply chain after a package leaves the last distribution point (store, warehouse, etc.) until it reaches an end customer. This final step towards the end customer is usually made in an urban area, with multiple stops along the way, which inevitably leads to delays. The most common delay factors are the following: long distances to travel to deliver small orders, traffic congestion, accidents, busy crosswalks, shortage of parking spaces, and unexpected breakdowns or assaults. These factors increase logistics costs due to higher fuel consumption, lower fleet utilization levels (in terms of the cargo moved), more staff hours, increased vehicle deterioration, merchandise deterioration or loss, etc. For these reasons, last-mile logistics represents a proportionally high fraction of logistics costs compared to long-distance transport (see, for example, the discussion in Özarık et al. (2021) and Wang et al. (2016)), and thus constitutes a topic widely studied in order to reduce inefficiencies.

Last-mile logistics also has a high impact on customer satisfaction. This stage is generally the first instance of direct contact between a product and a customer. Failures, delays, and complications in these activities can cause a customer not to buy from the same source again. Therefore, this phase is decisive for satisfaction and loyalty of end customers. Customer satisfaction often results from consistent service (Kovacs et al., 2014). And, in general, a consistent service can be achieved through: (i) consistency in the person serving the customer, (ii) consistency in the time the service is performed, and (iii) consistency in the quantity delivered or in the inventory level maintained at the customer’s location. Maintaining a consistent service also contributes to improved job satisfaction of vehicle drivers.

Advantages of using a TD-driven methodology to solve the last-mile logistics problem, i.e., assigning to each driver a fixed geographical zone that they should attend, are well documented. For instance, in Jarrah and Bard (2012), it is argued that making routing decisions based on territory design leads companies to more efficient distribution operations, generating several benefits for the drivers and the company. With a stable work area, the drivers are comfortable with their routes, which leads to better reliability and shorter service times. On the other hand, a fixed customer-to-driver assignment allows the customers to become familiar with the drivers, increasing customer satisfaction. Similarly, in Schneider et al. (2015), it is pointed out that maintaining a fixed driver that regularly visits a constant set of customers allows them to become familiar with their territory and their customers. This contributes to the driver serving their customers more efficiently, because experienced drivers know shortcuts, anticipate congestion problems, and find parking spots more quickly, reducing travel and customer service times. Additionally, in Oliveira et al. (2015), it is argued that insecurity of public roads and risk of load thefts are making companies look for systems able to detect when a vehicle leaves its planned route or distribution area. Most of existing tracking systems use techniques of virtual fences known as geofences: systems that detect anomalous behavior of vehicles. In such a system, each vehicle is assigned a geographical area, with its boundary defined as its geofence, that corresponds to its normal operation. Real-time GPS tracking allows to raise an alert each time a vehicle crosses its geofence — in case of such an event, the operations center contacts the driver to verify the reasons of the deviation and acts upon them. Contiguous and compact territories lead to good geofences.

The TD problem studied in this paper is motivated by a real-world application at a food company in Chile. This company is one of the leading national producers and marketers of meat and poultry. The company has seventeen distribution centers throughout the national territory. In this paper, we focus on just one of them. However, this study could be replicated at any of its distribution centers since their operations are quite similar throughout the country. The company has large sales volumes nationwide, and the costs associated with distribution activities represent an essential component of its total expenditures. Therefore, a 5 or 10 percent reduction in routing costs would already mean a significant improvement for the company.

In this work, the company’s customers correspond to supermarkets, restaurants, wholesalers, and small convenience stores spread throughout a region of Chile. The set of customers changes, on average, by 10% from one month to another. This customer variability is mainly due to the low frequency and irregularity of orders from small convenience stores, which represent 60% of the total number of customers. Also, the set of customers is characterized by high differences in service times. Even under perfect conditions, the time needed to unload the delivery can differ by about an hour from one customer to another. Additionally, each customer requires that their orders be delivered within a certain time window. The customers place their orders only one day in advance. The company has a fleet of vehicles dispatched from the distribution center to the customers. Each vehicle has a fixed subset of customers assigned to it. On each day, the vehicles visit their corresponding customers that require service.

We say that a customer is active on a particular day if they require delivery. Due to high variability in customers’ activity (the number of days between consecutive orders for each customer is highly irregular), ordered quantities, and service times, the company experiences significant problems in the fulfillment process during periods of high activity (days for which many customers place orders): customers’ time windows may not be respected and, in some cases, delivery even has to be postponed to another day. Moreover, the company experiences vehicle hijacking cases, where criminals take control of a vehicle to steal the goods, and then abandon the vehicle in some remote place. Consequently, the company needs to develop a decision support system that would improve the planning, scheduling, and control of freight distribution, seeking the right balance between operational costs, service quality, and security.

In this scenario, the construction of territories to define daily routing plans that do not overlap with each other is a desirable feature for the company. Design of territories allows the company to determine the best way to attend and respond quickly to new customer demands, standardize service quality, and organize efficient and equitable allocation of new customers among its different drivers. It is also a valuable characteristic for the company’s management due to the ease of establishing service contracts with third-party transportation companies based on general territories and not on particular sets of customers spread over different urban areas (which would be unattractive for a transportation company). Finally, establishing territories makes it easier to keep track of the vehicles in real-time, quickly detecting a change in the pattern of vehicle trips and stops, alerting about a possible accident, breakdown, theft, or hijacking of a vehicle.

The contributions of this paper are threefold. First, we analyze a real-world distribution system case at a major Chilean food company. High variability of demand experienced by the company make it unpractical to use traditional TD methodologies (see Kalcsics and Ríos-Mercado (2019) and Ríos-Mercado (2020)) that do not consider day-to-day routing in detail. In contrast, we propose a TD-driven methodology to generate routing plans organized in two steps. In Step 1, at the tactical level, we define territories with feasible routing plans based on past data (so with the demand known a priori). In Step 2, we use these territories at the operational level to organize day-to-day routing with only minor adaptations of the assignments obtained in Step 1. To the best of our knowledge, few works present territory definition methodologies that consider daily routing. And even fewer do this with real-world instances.

Second, we propose Territory Design for the Multi-Period Vehicle Routing Problem with Time Windows (TD-MPVRPTW), a new model for the territory definition problem that assures feasible routing plans for each day of the planning horizon, based on demand known in advance. We offer a MILP formulation and a heuristic algorithm to find good solutions for the model, both obtained by adding territory considerations to the ones proposed in Lespay and Suchan (2021). Handling of the contiguity and compactness restrictions presents significant computational challenges. Therefore, we offer adaptations of the solution methods from Lespay and Suchan (2021).

Finally, we analyze the quality of the territories computed by the proposed heuristic on the past demand of one month, when used to organize the day-to-day routing in the company under study during the following month: with the set of customers that place an order and the required quantities known only one day in advance. The evaluation shows that the methodology we propose yields good results for the company under study.

Considering routing aspects during districting at the tactical level and making only small changes for operational tour planning is beneficial for many practical applications. Unfortunately, traditional research on territory design with routing considerations tends to rely on estimations (see, for example, the discussion in Franceschetti et al. (2017)), like those coming from the Beardwood–Halton–Hammersley formula (Beardwood et al., 1959), but real-world instances, like the ones that we study in this paper, often present characteristics that are far from the assumptions of such TSP tour length estimation theorems. As a consequence, territories obtained with traditional techniques often yield customer-to-driver assignments that do not permit feasible routing (it is the case for our real-world instances). So, like for many other problems in operations research, combined consideration of different stages of decision making is important for districting. The purpose of this work is to fill this gap.

The remainder of this paper is organized as follows. Section 2 gives a literature review of TD for freight distribution. Section 3 presents a description of the problem. Section 4 describes our solution framework. Section 5 reports the results of computational experiments. Finally, Section 6 presents the conclusions.