Keywords

1 Introduction

In many real life physical distribution systems, the delivery orders are periodic. In these systems, the distribution firm delivers goods to a fixed set of customers. In a given T-day period, each customer must be visited at least once, with some customers requiring several visits for which minimum and maximum intervals are imposed on any two successive deliveries. The distribution firm is interested in developing a set of daily delivery routes for the T-day period so that a certain criterion is optimized, while guaranteeing that each customer receives deliveries at the required frequency (the number of deliveries). This kind of problem is called periodic vehicle routing problem (PVRP). PVRP arises in various settings such as waste collection (Beltrami and Bodin 1974, Bommisetty et al. 1998; Coene et al. 2010), industrial gas distribution (Bell et al. 1983; Dror and Ball 1987), soft drink and beer distribution (Golden and Wasil 1987) and linen deliveries in hospitals (Banerea-Brodeur et al. 1998). Our study was motivated by the problem faced by a distribution center that delivers frozen food to restaurants. Each restaurant needs two deliveries a week. While they may accept deliveries on any days of the week, they require that the deliveries should be spaced over time as evenly as possible considering the freshness of the food and the storage capacity limit.

The subject of PVRP is the integration, in a unified model, of some related components of the decision making process in managing the distribution activities of a firm, such as the fleet size determination, the scheduling of the deliveries and the routing of vehicles. It is thus a multilevel combinatorial optimization problem. The periodicity requirement sets links between the deliveries of different days. Therefore, the decision problem for the deliveries of 1 day cannot be solved separately from those for other days in the period.

PVRP is often viewed as an extension of the classical vehicle routing problem (VRP) from 1 day to a T-day period with the objective of minimizing the total distance traveled over the period. Classical formulations of PVRP can be found in Christofides and Beasley (1984) and Ball (1988). Francis et al. (2007) considered service flexibility in the problem including the choice of customer delivery frequencies. Archetti et al. (2017) introduced a flexible PVRP to minimize the total routing cost, where each customer has a total demand for the planning period and there is a limit on the maximum delivery quantity at each visit instead of having a fixed delivery frequency. Michallet et al. (2014) addressed a highly constrained PVRP where visits to each customer must be within the customer’s time window, no waiting is allowed and the arrival times of any two visits to the same customer must be separated by at least a minimum time interval.

Most of the solution methodologies for classical PVRP follow the line of an assigning-then-routing approach. That is, the customers are assigned to days of the T-day period first and the resulting VRP for each day is then solved. After this an improvement stage follows to exchange the customers between days or between the routes of the same day to minimize the total travel distance over the period. For any assignment of customers to the days in the period, the subproblem for each day is a classical VRP problem which is NP-hard implying that it is unlikely to have an efficient method to solve it optimally. In search for a good assignment of customers to different days, a large number of VRPs need to be solved. To make it computationally feasible, heuristics are used for the decisions.

Different heuristics have been developed to solve PVRP. Christofides and Beasley (1984) proposed two heuristics in which different relaxations of the VRP subproblem (p-median relaxation problem and traveling salesman relaxation problem) for each day was solved. Tan and Beasley (1984) developed heuristics based on the generalized assignment relaxation problem in which K⋅T seed points were chosen, where K is the number of vehicles for each day and T is the number of days in the period. Russell and Gribbin (1991) gave a four-stage heuristic to evaluate the results of different combinations for each day. Chao et al. (1995) tried to first balance the total amount of customer demand in each day by solving an integer programming problem that minimizes the maximum total amount of demand delivered in a single day, and then to form vehicle delivery routes for each day. Following this, a one-point movement method was adopted to make further improvement. Metaheuristics such as tabu search (Cordeau et al. 1997) and genetic algorithm (Drummond et al. 2001), and scatter search (Alegre et al. 2007) have also been applied for solving PVRP. Alonso et al. (2008) studied a PVRP allowing multiple trips for each vehicle and considering the accessibility constraints. They used an assigning-then-routing heuristic to generate an initial solution and then used tabu search for improvement to minimize total travel cost. Rahimi-Vahed et al. (2013) solved a multi-depot PVRP problem using a path relinking algorithm while Nguyen et al. (2014) proposed a hybrid genetic algorithm for PVRP with time windows. Cacchiani et al. (2014) presented a hybrid algorithm embedding both heuristic and exact components, and used it to solve PVRP where each customer needs to be served on a combination of days chosen from a set of valid day combinations. The objectives of the problems in the above three studies are also to minimize the total travel cost.

Shih and Lin (1999) and Shih and Chang (2001) used a routing-then-scheduling approach to solve the problem of collecting infectious wastes from hospitals. The problem is quite special where collection needs to be made only once in each 1-week period from every hospital. They first solved a standard vehicle routing problem to determine a set of individual routes for the collection. Mixed integer programming was then used to assign the routes to particular days of the week with the objective of minimizing either the maximal daily travel or the difference between the maximal and the minimal daily travels.

Although the objective to minimize the total distance traveled is important as it reduces the fuel costs, minimization of the fleet size (the maximum number of vehicles used for any 1 day) is often the primary objective for many delivery firms. This is because the fixed costs associated with the number of vehicles (capital investment, maintenance, wages, insurance, etc.) often outweigh the costs related to mileage. The exact settings of a PVRP may be different for different applications. Gaudioso and Paletta (1992) studied a PVRP with the objective of minimizing the fleet size and presented a model assuming that the planning horizon is divisible by the delivery frequencies of all customers. They proposed a heuristic algorithm that allocates deliveries of one customer at a time. Since there is no limit on daily travel distance or time, a bin-packing problem is solved for each day to determine the number of vehicles needed to serve the customers assigned to that day. When assigning the deliveries of each customer, the objective is to minimize the fleet size increase. Rahimi-Vahed et al. (2015) addressed a multi-depot PVRP to minimize fleet size. They considered a list of allowable visit patterns for each customer, as well as vehicle capacity, route duration and budget constraints. A modular heuristic algorithm was proposed to solve the problem.

Most previous studies on PVRP tried to minimize traveling cost. Only a few considered minimizing fleet size as objective. In addition, the majority of the PVRP studies assume that each customer has a given list of possible delivery patterns. In many practical situations such as the frozen food delivery problem mentioned earlier, the actual delivery days to a customer can be flexible but the deliveries need to be evenly spaced considering freshness of the food and storage capacity of the customer. In this chapter we study the PVRP with these features and allow different delivery frequencies for different customers.

Our problem is stated as follows. A distribution center delivers goods to a fixed set of customers periodically. One period includes T days. A customer needs at most one delivery on any day. If a customer requires E deliveries over the T-day period, we say that the delivery frequency of this customer is E. For all the customers, there is a total of n different delivery frequencies, E1, …, En. Without loss of generality, we assume 1 ≤ E1 < E2 <, … , < En ≤ T. The required delivery amount (the demand) for the same customer is the same for every delivery. The delivery days for the same customer must be distributed in the period as evenly as possible. That is, any two successive deliveries must be spaced at least ⌊T/Ei⌋ days and at most ⌈T/Ei⌉ days for a delivery frequency Ei. We will refer to this requirement as evenly-spacing requirement. Homogeneous vehicles are used to make the deliveries. The problem is to assign, over a delivery period T, a feasible combination of delivery days to each customer and to schedule the deliveries for every day in the period in order to minimize the fleet size.

The evenly-spacing requirement for the delivery days is consistent with the practice of many delivery problems, such as the problem of food delivery to restaurants in the example mentioned earlier. Moreover, to make practical implementation of the solution easier, we further make the assumption below.

Assumption 1

While customers can be grouped with any other customers in a delivery route, it is required that every delivery of any particular customer is made in a route with the same set of other customers.

Solutions under this assumption have practical advantages. The delivery route for every delivery to a customer is always the same. Therefore the customer can expect delivery around the same time on every delivery day and thus can be better prepared for receiving. This assumption can also make the delivery team more familiar with the routes and make the fleet management in the delivery firm easier.

The periodical nature of the delivery orders makes the daily delivery orders change in a cyclical pattern. Our task is therefore to schedule deliveries for one period. Then the schedule can be followed in every period.

In the remaining parts of this chapter, we first study the periodical delivery problem with the same delivery frequency, propose a routing-then-scheduling approach for the problem and analyze the performance of the solution. The method can be used to solve the problem in situations where the delivery frequencies required by all customers are the same. Based on the above analysis, the general problem with different delivery frequencies is studied. A general integer programming model is formulated and a two-stage method using two smaller integer programming models is proposed for more stable and efficient solution. An extended routing-then-scheduling approach is also presented to solve problems without assumption 1. Computational experiments testing the performance of the methods are then reported. Finally conclusion remarks are given.

2 Problem with the Same Delivery Frequency for All Customers

2.1 A Routing-then-Scheduling Approach

For the periodical delivery problem with the same delivery frequency E, two successive deliveries to the same customer must be spaced at least ⌊T/E⌋ days and at most ⌈T/E⌉ days. This special problem would not be solved effectively and efficiently if we followed the conventional procedures for a general PVRP: assigning customers to delivery days and then routing each day separately. In the improvement stage of the conventional heuristic procedure, it is hard to choose which customers should be moved because all the customers have the same delivery combination.

However, the special characteristics of this problem can be used to develop more efficient algorithms. We propose a routing-then-scheduling approach to solve the problem in two phases:

  • Phase 1. Solve a VRP to minimize fleet size, considering all the customers as if every customer requires a delivery on the same day. We will call the set of customers served by one vehicle in a day a route. Then the result of this VRP will be a set of delivery routes.

  • Phase 2. Assign these routes to delivery days over the T-day period. Each route will be assigned E times, spaced evenly over the period.

Here a route is viewed in a broad sense. It does not necessarily mean one physical vehicle trip. In particular, given the vehicle capacity, multiple trips may be performed by a vehicle within the limit of the working time in a day. A route here refers to all the delivery work done by one vehicle for 1 day, which includes all the trips of the vehicle and the associated loading and unloading activities in a day.

VRP has received extensive study. Many existing algorithms can be borrowed to solve the above phase-one problem (e.g., Achuthan et al. 1998; Vanderbeck 1999). In this chapter, we will not include this phase in the presentation of the algorithms. Instead, we will concentrate on the phase-two problem of scheduling the routes over the T-day period when the algorithms are developed.

In scheduling the delivery routes, any two successive deliveries of the same route must be spaced at least ⌊T/E⌋ days and at most ⌈T/E⌉ days. Note that this restriction also applies to the last delivery in one period and the first in the next period. If T is a multiple of E, any two successive deliveries of the same route are spaced exactly T/E (= ⌊T/E⌋ = ⌈T/E⌉) days. If T is not a multiple of E, ⌈T/E⌉ = ⌊T/E⌋ + 1.

2.2 An Algorithm for Route Scheduling

Let P denote the optimal number of routes, obtained in the routing phase, which include all the customers exactly once. With the delivery frequency E, each route must be delivered E times in the planning period. We refer to each delivery of a route as a route-delivery. Then totally (E⋅P) route-deliveries are required in the period to serve all the customers E times. On average, the number of routes delivered in each day is (E⋅P/T). Thus, to balance the workloads on different days and hence minimize the fleet size, the number of routes delivered in each day should be either ⌊E⋅P/T⌋ or ⌈E⋅P/T⌉ routes.

We number the P different routes as 1, 2, …, P. We further number each of the E⋅P route-deliveries uniquely as follows:

$$ k=j+m\cdot P,\kern0.5em j=1,2,\dots, P,\kern0.5em m=0,1,\dots, E\hbox{--} 1. $$

where j is route numbers, k is a route-delivery number. Therefore, j + m1 ⋅ P and j + m2 ⋅ P (m1 ≠ m2, 0 ≤ m1 ≤ E – 1, 0 ≤ m2 ≤ E – 1) represent the same route j delivered on different days. While each of the P routes will be delivered E times in the T-day period, each of the E⋅P route-deliveries will be made exactly once in the T-day period. For illustration, consider an example problem in which three deliveries are required to each customer in a 5-day period and delivering to all customers once needs four routes, i.e., T = 5, P = 4, E = 3. Table 1 presents a delivery schedule and shows the relationship between the 4 routes and the 12 route-deliveries. To schedule the E⋅P route-deliveries to the T days in the period, we need to determine which days to have ⌊E⋅P/T⌋ route-deliveries and which days to have ⌈E⋅P/T⌉ route-deliveries in order to satisfy the delivery spacing requirement, because our approach does not have the restriction in Gaudioso and Paletta (1992) that requiring the planning period to be a multiple of the delivery frequency.

Table 1 Routes and route-deliveries for an example problem with T = 5, P = 4, E = 3.
Full size table

We present below a scheduling procedure that determines the assignment of the route-deliveries to each day in the period. The procedure considers 1 day at a time. In the procedure, i is the day number, fi is the number of routes assigned to day i, f0 is the accumulated number of assigned route-deliveries up to day i, f is the fleet size.

Algorithm 1

  • Step 1: f0 = 0, f = 0, i = 1.

  • Step 2: fi = ⌊i⋅P⋅E/T – f0⌋; assign the next fi route-deliveries to day i; if fi > f, then let f = fi.

  • Step 3: If i < T, then f0 = f0 + fi, i = i + 1, go to step 2; otherwise, stop. f is the fleet size.

This algorithm is computationally very efficient. Its computational complexity is O(max{P⋅E, T}).

2.3 Properties of the Solution

Algorithm 1 addresses the evenly-spacing requirement for the deliveries of the same route implicitly. We prove now the solution produced by this algorithm is indeed feasible, i.e., satisfying this requirement.

Proposition 1

The schedule generated by Algorithm 1 is a feasible solution to the problem, i.e., any two successive deliveries of a route in the schedule are ⌊T/E⌋ or ⌈T/E⌉ days apart.

Proof

Consider any route R1 that is scheduled on day i, and its position on that day is r (it is the rth route among those assigned to that day). Then its route-delivery number is ⌊(i – 1)⋅P⋅E/T⌋ + r. Let k be the first day on which route R1 is scheduled after day i, and the position of route R1 on day k is s. Then the route-delivery number can be represented as ⌊(k – 1)⋅P⋅E/T⌋ + s. Based on the algorithm procedure, we have the following relations.

  1. (i)

    ⌊(i – 1)⋅P⋅E/T⌋ + r + P = ⌊(k – 1)P⋅E/T⌋ + s ≤ k⋅P⋅E/T

    • ⇒ (i – 1)⋅P⋅E/T – 1 + r + P < k⋅P⋅E/T

    • ⇒ (i – 1)⋅P⋅E/T + P < k⋅P⋅E/T

    • ⇒ P – P⋅E/T < (k – i)P⋅E/T

    • ⇒ T/E – 1 < k – i

    • ⇒ ⌊T/E⌋ ≤ k – i.

  2. (ii)

    ⌊(k – 1)P⋅E/T⌋ + s = ⌊(i – 1)⋅P⋅E/T⌋ + r + P ≤ i⋅P⋅E/T + P

    • ⇒ (k – 1)P⋅E/T – 1 + s < i⋅P⋅E/T + P

    • ⇒ (k – 1)P⋅E/T < i⋅P⋅E/T + P

    • ⇒ (k – i)P⋅E/T < P + P⋅E/T

    • ⇒ k – i < T/E + 1

    • ⇒ k – i ≤ ⌈T/E⌉.

Therefore, any two successive deliveries of a route in the schedule are ⌊T/E⌋ or ⌈T/E⌉ days apart, i.e., the schedule is feasible.□

In the following the optimality of Algorithm 1 is analyzed.

Proposition 2

In the solution generated by Algorithm 1, the number of routes delivered in each day is either ⌊E⋅P/T⌋ or ⌈E⋅P/T⌉. The fleet size required for the delivery is therefore ⌈P⋅E/T⌉.

Proof

For any day i in the schedule, the number of vehicles needed (number of routes scheduled) is fi = ⌊i⋅P⋅E/T – ⌊(i – 1)P⋅E/T⌋ ⌋ < ⌊i⋅P⋅E/T – (i – 1)P⋅E/T + 1⌋ = ⌊P⋅E/T + 1⌋. This implies that fi ≤ ⌈P⋅E/T⌉.

Similarly, fi = ⌊i⋅P⋅E/T – ⌊(i – 1)P⋅E/T⌋ ⌋ ≥ ⌊i⋅P⋅E/T – (i – 1)P⋅E/T ⌋ = ⌊P⋅E/T ⌋.

Therefore, ⌊P⋅E/T ⌋ ≤ fi ≤ ⌈P⋅E/T⌉.

That is, the number of routes delivered in each day is either ⌊E⋅P/T⌋ or ⌈E⋅P/T⌉. As the number of routes to be delivered is at most ⌈E⋅P/T⌉, the fleet size required is ⌈P⋅E/T⌉.□

Proposition 3

Under Assumption 1, the solution generated by Algorithm 1 is optimal provided that the VRP considering deliveries to all customers once is solved optimally.

Proof

P is the minimum number of routes for one delivery to all customers resulted from the VRP. Under the Assumption 1, the total number of deliveries needed for all routes in the period is E⋅P. The minimum fleet size required to cover these routes in the T-day period is then ⌈E⋅P/T⌉. According to Proposition 2, the number of routes assigned by Algorithm 1 to any day is at most ⌈E⋅P/T⌉. Therefore, the solution is optimal.□

The customer orders are delivered E times in the period. Due to the requirement for delivery days of any order being evenly distributed, a new round of delivery will not start on a day if previous round has not completed on that day or the day before. Orders from two successive rounds may only be delivered on the same day for 1 day. Similar to the above proof, it can be shown that if customers of one round cannot be mixed with those of next round within a route, then the solution is optimal even without Assumption 1. In practice, the routing problem may be solved heuristically. In this case the final solution may not be optimal. The solution quality will depend on the quality of routing problem solution.

2.4 Alternative Schedules with the Same Fleet Size

Algorithm 1 generates one feasible schedule for the same-frequency problem with optimal fleet size. If (P⋅E)/T is integer then every day is assigned (P⋅E)/T routes and this optimal solution is unique. If (P⋅E)/T is not integer, there exist alternative feasible optimal solutions. In practice, the distribution company may be interested in these alternative solutions so that they have freedom to choose on which days of the period the number of ⌊E⋅P/T⌋ or ⌈E⋅P/T⌉ vehicles are scheduled based on availability of resources (vehicles, drivers). Furthermore, the alternative solutions will be useful when we deal with the problem with different delivery frequencies. The proposition below provides properties based on which we can generate alternative optimal feasible solutions.

Proposition 4

Given that the route-deliveries are assigned day-by-day sequentially according to their numbering and that every day is assigned at least ⌊P⋅E/T⌋ and at most ⌈P⋅E/T⌉ route-deliveries, any schedule with the following property is feasible:

  • Case 1, T is a multiple of E: Exactly P routes are assigned in the first T/E-day sub-period with each day assigned at most ⌈(P⋅E)/T⌉ routes, and the same pattern repeats in each of the following T/E-day sub-periods;

  • Case 2, T is not a multiple of E: Any two successive ⌈(P⋅E)/T⌉-route days are spaced either ⌊T/R⌋ or ⌈T/R⌉ days, and at most ⌈(⌈T/E⌉ – 1)R/T⌉ days are assigned ⌈(P⋅E)/T⌉ routes in any (⌈T/E⌉ – 1) days and at least ⌊⌈T/E⌉R/T⌋ days are assigned ⌈(P⋅E)/T⌉ routes in any ⌈T/E⌉ days, where R = mod (P⋅E, T) and thus P⋅E = T ⌊P⋅E/T⌋ + R = R ⌈(P⋅E)/T⌉ + (T – R) ⌊P⋅E/T⌋.

Proof

Case 1: With the property specified, it can be seen that two successive deliveries of the same route are always spaced T/E days, i.e., two successive deliveries for any customer are always T/E days apart. So the schedule is feasible.

Case 2: In any (⌈T/E⌉ – 1) days the number of route-deliveries is at most

$$ {\displaystyle \begin{array}{l}\left(\left\lceil T/E\right\rceil -1\right)\left\lfloor P\cdot E/T\right\rfloor +\left\lceil \left(\left\lceil T/E\right\rceil -1\right)R/T\right\rceil \\ {}=\left\lceil \left(\left\lceil T/E\right\rceil -1\right)\left\lfloor P\cdot E/T\right\rfloor +\left(\left\lceil T/E\right\rceil -1\right)R/T\right\rceil \\ {}=\left\lceil \left(\left\lceil T/E\right\rceil -1\right)\left(\left\lfloor P\cdot E/T\right\rfloor +R/T\right)\right\rceil \\ {}=\left\lceil \left(\left\lceil T/E\right\rceil -1\right)P\cdot E/T\right\rceil \\ {}<\left\lceil \left(T/E\right)P\cdot E/T\right\rceil =P\end{array}} $$

In any ⌈T/E⌉ days the number of route-deliveries is at least

$$ {\displaystyle \begin{array}{l}\left\lceil T/E\right\rceil \cdot \left\lfloor P\cdot E/T\right\rfloor +\left\lfloor \left\lceil T/E\right\rceil \cdot R/T\right\rfloor \\ {}=\left\lfloor \left\lceil T/E\right\rceil \cdot \left\lfloor P\cdot E/T\right\rfloor +\left\lceil T/E\right\rceil \cdot R/T\right\rfloor \\ {}=\left\lfloor \left\lceil T/E\right\rceil \cdot \left(\left\lfloor P\cdot E/T\right\rfloor +R/T\right)\right\rfloor \\ {}=\left\lfloor \left\lceil T/E\right\rceil \cdot P\cdot E/T\right\rfloor >\left\lfloor \left(T/E\right)\cdot P\cdot E/T\right\rfloor =P\end{array}} $$

Two successive deliveries to any customer are in two route-deliveries that are P apart. The above relations indicate that the two routes are assigned at least ⌊T/E⌋ days apart and at most ⌈T/E⌉ days apart. Therefore, the schedule is feasible.□

Corollary 1

The evenly-spacing requirement is satisfied if the number of route-deliveries does not exceed P in any successive ⌊T/E⌋ days and does not fall below P in any successive ⌈T/E⌉ days.

3 Problem with Different Delivery Frequencies

Under Assumption 1, customers with different delivery frequencies cannot be mixed in the same route. To solve the problem with different delivery frequencies, we can still take the two-phase routing-then-scheduling approach. In phase 1, we first solve a VRP for each delivery frequency Ei to obtain the number of routes needed, Pi, for one delivery to all the customers with this frequency. The total number of route-deliveries for this frequency is then Ei⋅Pi. The remaining task in phase 2 is then to make feasible assignments of all the route-deliveries for all frequencies to the days in the T-day period so that the fleet size is minimized. In the following two subsections, we present two methods for solving the phase-2 problem.

3.1 A General Integer Programming Model

We define the following variables.

  • yij = the number of route-deliveries for frequency Ei assigned on day j, i = 1,…,n, j = 1, …, T.

  • FZ = the fleet size.

Then the problem can be formulated as the integer programming model below.

$$ \left(\mathbf{IP0}\right) \operatorname {Minimize}\ FZ $$
(1)

Subject to

$$ FZ\ge \sum \limits_{i=1}^ny{}_{ij},\kern1em j=1,\dots, T $$
(2)
$$ \sum \limits_{j=1}^T{y}_{ij}={P}_i\cdot {E}_i,\kern1em i=1,\dots, n $$
(3)
$$ \sum \limits_{j=h}^{h+\left\lfloor T/{E}_i\right\rfloor -1}{y}_{i,\operatorname{mod}\left(j-1,T\right)+1}\le {P}_i,\kern1em i=1,\dots, n;h=1,\dots, T;{E}_i\ne 1 $$
(4)
$$ \sum \limits_{j=h}^{h+\left\lceil T/{E}_i\right\rceil -1}{y}_{i,\operatorname{mod}\left(j-1,T\right)+1}\ge {P}_i,\kern1em i=1,\dots, n;h=1,\dots, T;{E}_i\ne 1 $$
(5)
$$ {y}_{ij}\ge 0\ \mathrm{and}\ \mathrm{integer},i=1,\dots, n,j=1,\dots, T $$
(6)

In the model, the objective (1) is to minimize the fleet size required. Constraints (2) ensure that the number of routes delivered on each day does not exceed the fleet size. Constraints (3) guarantee that all the orders for each frequency are delivered. Constraints (4) and (5) guarantee that the schedule is feasible, i.e., any two successive deliveries of a route for a frequency (the two deliveries are numbered Pi apart) are delivered on 2 days that are either ⌈T/Ei⌉ or ⌊T/Ei⌋ apart. Note that these constraints are unnecessary for frequency 1 because orders with frequency 1 can be delivered on any 1 day in the period. Constraints (6) are nonnegative and integer constraints.

3.2 A Two-Stage Method

The above model minimizes the fleet size. In an optimal solution, however, the number of routes for a particular frequency assigned on different days can be significantly different. Therefore, yij may take any value from 0 to Pi. This implies that the delivery patterns (the number of routes delivered each day for each frequency) are sensitive to both adding (removing) a delivery frequency and the route variation for existing frequencies. For example, adding a new delivery frequency or reducing one route for a certain delivery frequency can cause the delivery patterns for other frequencies change greatly. To alleviate this drastic change, we limit the number of routes assigned to a day for delivery frequency Ei (Ei ≠ 1) to be either ⌈PiEi/T⌉ or ⌊Pi⋅Ei/T ⌋. Then we can use the following binary variable, rather than a general integer variable, to represent the assignment of routes for a frequency to a day.

$$ {x}_{ij}=\left\{\begin{array}{ll}1,& \mathrm{if}\ \left\lceil {P}_i{E}_i/T\right\rceil\ \mathrm{routes}\ \mathrm{for}\ \mathrm{frequency}\ {E}_i\ \mathrm{are}\ \mathrm{assigned}\ \mathrm{on}\ \mathrm{day}\ j\\ {}0,& \mathrm{if}\ \left\lfloor {P}_i{E}_i/T\right\rfloor\ \mathrm{routes}\ \mathrm{for}\ \mathrm{frequency}\ {E}_i\ \mathrm{are}\ \mathrm{assigned}\ \mathrm{on}\ \mathrm{day}\ j\end{array}\right.,\kern1em i=1,\dots, n,j=1,\dots, T,{E}_i\ne 1. $$

Then we can obtain a solution in two stages.

The first stage tries to minimize the fleet size requirement FZ1, considering the routes with frequencies other than 1. The following 0-1 integer programming model does this using the above defined binary variables.

$$ \left(\mathbf{IP1}\right) \operatorname {Minimize}\ FZ1 $$
(7)

Subject to

$$ FZ1\ge \sum \limits_{\begin{array}{l}\ i=1\\ {}{E}_i\ne 1\end{array}}^nx{}_{ij}+\sum \limits_{\begin{array}{l}\ i=1\\ {}{E}_i\ne 1\end{array}}^n\left\lfloor {P}_i{E}_i/T\right\rfloor, \kern1em j=1,\dots, T $$
(8)
$$ \sum \limits_{j=1}^T{x}_{ij}=\operatorname{mod}\left({P}_i{E}_i,T\right),\kern1em i=1,\dots, n;{E}_i\ne 1 $$
(9)
$$ \sum \limits_{j=h}^{h+\left\lfloor T/{E}_i\right\rfloor -1}{x}_{i,\operatorname{mod}\left(j-1,T\right)+1}\le \left\lceil \left\lfloor T/{E}_i\right\rfloor \operatorname{mod}\left({P}_i{E}_i,T\right)/T\right\rceil, \kern1.25em i=1,\dots, n;h=1,\dots, T;{E}_i\ne 1 $$
(10)
$$ \sum \limits_{j=h}^{h+\left\lceil T/{E}_i\right\rceil -1}{x}_{i,\operatorname{mod}\left(j-1,T\right)+1}\ge \left\lfloor \left\lceil T/{E}_i\right\rceil \operatorname{mod}\left({P}_i{E}_i,T\right)/T\right\rfloor, \kern1em i=1,\dots, n;h=1,\dots, T;{E}_i\ne 1, $$
(11)
$$ {x}_{ij}=\left\{0,1\right\},i=1,\dots, n;j=1,\dots, T;{E}_i\ne 1 $$
(12)

The meanings of the constraints are similar to the corresponding constraints in the earlier IP (integer programming) model. Note that feasibility constraints (10) and (11) use the property given in Proposition 4. After solving this model, we can get the total number of routes assigned to each day, Fj, j = 1,…,T, for all the frequencies other than 1.

The second stage is to assign the routes with frequency 1 on those days with fewer routes based on the solution to the first stage model so that the total fleet size can be minimized. Let P1 denote the total number of routes for frequency 1. Define variable yj as the number of routes for frequency 1 assigned to each day j = 1,…,T. The second stage problem can then be formulated as the small IP model below.

$$ \left(\mathbf{IP2}\right) \operatorname {Minimize}\ FZ $$
(13)

Subject to

$$ FZ\ge {F}_j+{y}_j,\kern1em j=1,\dots, T $$
(14)
$$ \sum \limits_{j=1}^T{y}_j={P}_1 $$
(15)
$$ {y}_j\ge 0\ \mathrm{and}\ \mathrm{integer},j=1,\dots, T. $$
(16)

Constraints (14) ensure that the fleet size is sufficient to cover all routes assigned to each day including those with frequency 1. Constraint (15) requires that all routes with frequency one are assigned. Constraints (16) are nonnegative and integer constraints.

Both the general IP model (IP0) and the two-stage models (IP1 and IP2) are standard IP models, which can be solved using a standard software package.

3.3 An Extended Routing-then-Scheduling Approach

Assumption 1 allows us to schedule routes rather than individual customers in the scheduling phase. This makes the problem simpler and the model size much smaller. Even in the situation where Assumption 1 does not holds, if the numbers of routes for different frequencies generated in phase 1 are large and the routes are all close to the vehicle’s capacity of a day, then there may not be much room left for improvement by reorganizing the routes. Therefore the solution obtained under the assumption will be a close-to-optimal solution for the problem in this situation. If the number of routes is small and they are not close to the vehicle’s capacity, then a better solution may be obtained using the following extended routing-then-scheduling approach.

  • Phase 1. Solve a VRP for each delivery frequency Ei to obtain the number of routes needed, Pi, for one delivery to all the customers with this frequency. While keeping the number of routes needed to a minimum, try to minimize the workload of the last route.

  • Phase 2. Use the two-stage method to schedule the Ei deliveries of the first (Pi – 1) routes, and the Pith route if it is close to full capacity, for every frequency.

  • Phase 3. Schedule the Ei deliveries for individual customers in the unscheduled routes of all frequencies so that the total fleet size is minimized. The evenly-spacing requirement should be observed. Although the customers here are considered individually, the number of such customers is small given the objective of Phase 1. Therefore the problem of this phase is much simpler than the original problem.

4 Computational Experiments

4.1 Testing the Route Assignment Models

To test the performance of the models presented in the last section, we carry out numerical experiments on a variety of test problems with the planning period T set to 7, 14 and 30 days, which correspond to the common practice of weekly, bi-weekly and monthly delivery schedules respectively. For each T value, we consider several delivery frequencies in the delivery problem. For a delivery frequency, the number of routes required to make one delivery to all customers with this frequency is generated randomly from a uniform distribution [1, 2T]. Table 2 shows the parameter settings for the test problems.

Table 2 Parameter settings for the test problems
Full size table

For each value of the planning period T, we generate 10 problem instances. We solve each problem instance using both the general IP model (IP0) and the two-stage method with the first stage model (IP1) and the second stage model (IP2). The IP models are solved using ILOG CPLEX 10.2. Both methods take a very short time (in seconds) to solve a problem. For each problem instance, the fleet sizes obtained by the two methods are the same.

However, the delivery patterns generated by the two methods differ greatly. Especially, the delivery patterns generated by the two-stage method are less sensitive to problem parameter changes (changes in delivery frequency and route) than those by the general IP model. In the following, we illustrate the effects of parameter changes on the delivery patterns of the general IP model and the two-stage method using a problem instance with T = 7. The original problem has seven routes to be delivered once, nine routes to be delivered twice, ten routes to be delivered three times and one route to be delivered seven times in the 7-day period. Table 3 shows these data for the original problem and the numbers of routes for three variations of the problem.

Table 3 Number of routes for a problem instance with T = 7 and its variations
Full size table

For the data in Table 3, the number of routes for frequencies 1, 2 and 7 remain unchanged for all the variations considered. Because the frequency-7 route needs to be delivered every day and there is only one pattern for this, the delivery patterns for frequencies 1 and 2 are the best indicators to demonstrate the solution robustness of the models. Figures 1 and 2 show the delivery patterns generated by the general IP model and two-stage models, respectively, for the example problem instance and its variations.

Fig. 1
figure 1

Delivery patterns generated by the general IP model

Full size image
Fig. 2
figure 2

Delivery patterns generated by the two-stage models

Full size image

Based on Fig. 1, we can see that the delivery patterns generated by the general IP model change significantly whenever there is a change in delivery frequency or in the number of routes for a delivery frequency. That is, to guarantee the minimization of the fleet size, the number of delivery routes for the other frequencies (frequency 1 and frequency 2) must be adjusted significantly to accommodate the disturbances. However, the delivery patterns generated by the two-stage method (Fig. 2) are much more robust. For each frequency, the maximum variation of delivered routes for each day is 1, as the constraints of the model (IP1) show.

In summary, the two-stage method solves the route scheduling problem very effectively. It gives optimal solutions for all the problems tested and the delivery patterns generated are more robust than those generated by the general IP model. In addition, the models in the two-stage method are much simpler and can solve large problems when the planning period is long and there are more different delivery frequencies.

4.2 Test on Benchmark Examples

Detailed data for three standard VRPs with 50, 75 and 100 customers respectively were provided in Christofides and Eilon (1969) and in Eilon et al. (1971). Christofides and Beasley (1984) generated ten instances of PVRPs from these data by setting periodical patterns for customer demand. The feasible periodical demand patterns in these PVRPs match with our problem setting which requires the deliveries to each customer to be spaced over time as evenly as possible. Gaudioso and Paletta (1992) tested their method on some of these PVRPs in which all customers have a delivery frequency of 1. Six of the ten problems are PVRPs with delivery frequency of 1, labeled as 50a, 50c, 75a, 75c, 100a, 100c in Christofides and Beasley (1984). We solved these six problems using our routing-then-scheduling approach and obtained solutions with the same fleet sizes as in the solutions by Christofides and Beasley (1984) and Gaudioso and Paletta (1992). The total distances traveled depend on the method used in the routing phase. In the routing phase we used a location-allocation model to cluster the customers into routes heuristically and then use a traveling salesman problem model to determine the actual trip of each route. The resulting routes are then scheduled to the days in the period using Algorithm 1. Table 4 shows the results on these problems by our approach (L&R) together with those by Christofides and Beasley (1984) (C&B) and by Gaudioso and Paletta (1992) (G&P). Since our objective is to minimize the fleet size, the distance in our solution could be longer than that in the C&B solution in some cases. However, the results in Table 4 show that in terms of distance our solution is also comparable to the C&B solution.

Table 4 Results on the benchmark problems with delivery frequency of 1
Full size table

The rest four PVRPs in Christofides and Beasley (1984) are multi-frequency problems (labeled as 50b, 75b, 100b and 100d), all with a planning period of 5, generated by splitting the customers in the VRPs in Eilon et al. (1971) in groups requiring different delivery frequencies. These problems cannot be handled by the heuristic in Gaudioso and Paletta (1992). We applied our approach on these problems. Under Assumption 1, our method obtained solutions with the same fleet sizes as in the C&B solutions for problems 75b, 100b and 100d. For problem 50b, the solution with Assumption 1 needs a fleet size of 4, one more than in the C&B solution, while our extended routing-then-scheduling approach gives a solution with the same fleet size as in the C&B solution. This problem is an ideal example to illustrate the effect of Assumption 1 in an extreme situation, and hence worthy to discuss in detail. The planning period of the problem is 5 days. There are 50 customers in total, 17 of them with small demands need a delivery frequency of 1, 26 with medium demands need a delivery frequency of 2, and 7 with large demand need a delivery frequency of 5.

In the routing phase result, all the frequence-1 customers can be served in one route with about 80% full of the vehicle capacity; serving all the frequency-2 customers once needs 3 routes (two nearly full and one 70% full); and serving all the frequency-5 customers once needs two routes (one nearly full and one 36% full). Under Assumption 1, the total number of route-deliveries will be 1 + 3 × 2 + 2 × 5 = 17 and scheduling them in 5 days will need a fleet size of 4, even without considering the evenly-spacing requirement. Applying our extended routing-then-scheduling approach, we can first schedule the deliveries of the close-to-full routes: the frequency-1 route (let us call it Route 1), the two full frequency-2 routes (Routes 2 and 3) and the full frequency-5 route (Route 4). All these together need a fleet size of 2. For the remaining customers, the customers in the 36% full frequency-5 route (Route 5) need to be delivered every day. We can separate the customers in the 70% full frequency-2 route into two groups and schedule them in 4 days, each group on 2 days spaced evenly. For each of these 4 days, these customers can be delivered together with those in Route 5 on that day. Since the customers are added to Route 5 on these days, the enlarged Route 5 on these days will be renamed as Route 6 and Route 7 respectively. The complete route schedule is shown in Table 5, while Assumption 1 is partially respected in the solution. The final fleet size needed is 3.

Table 5 Route schedule given by our extended routing-then-scheduling approach for Problem 50b
Full size table

For relating the result easily to the problem data in Eilon et al. (1971) and Christofides and Beasley (1984), the customers in these routes are listed below.

  • Route 1: 1, 4, 10, 15, 17, 19, 21, 22, 24, 26, 29, 36, 37, 40, 45, 46, 50;

  • Route 2: 6, 13, 14, 23, 27, 43, 44, 47, 48;

  • Route 3: 5, 9, 11, 16, 30, 33, 38, 39, 42, 49;

  • Route 4: 12, 18, 25, 34, 41;

  • Route 5: 2, 20;

  • Route 6: 2, 20, 7, 8, 31, 32;

  • Route 7: 2, 20, 3, 28, 35.

The total distance travelled for the solution is 1967.1. If the customers in different routes on the same day can be mixed, we can mix all customers in different routes of each day together and solve a VRP to reorganize them into new routes. In this way the total distance can be shortened to 1586.3.

The above test on the benchmark problems shows that our approach is effective. We can also see that while Assumption 1 can simplify the problem and is convenient for the delivery team, it does not significantly affect the solution quality in the situation where this assumption is not required. In extreme cases where the assumption affects the solution, the problem can be solved effectively using our extended routing-then-scheduling approach to reduce the travel distance or cost while the fleet size remains the same or slightly improved. Managers can decide whether Assumption 1 should be observed in the specific situations.

5 Conclusions

In this chapter, we studied the periodical delivery problem in which delivery frequencies to different customers may be different, the deliveries to the same customer need to be evenly distributed over time and the objective is to minimize the fleet size. We first studied the problem with the same delivery frequency and proposed a routing-then-scheduling approach. Analysis was then done on the feasibility and optimality of the solution. Based on the result of the analysis, we then developed a general integer programming model and a two-stage method, with a smaller integer programming model for each stage, for the general problem with different delivery frequencies. The approach guarantees the resulting delivery plan satisfying the assumption that customers in the same route remain in the same route in every delivery. Such a plan is convenient for management and the delivery team. For the cases where this assumption is not necessary, we presented an extended routing-then-scheduling approach that can reduce traveling distance. Numerical experiments on problems with typical planning periods showed that both methods could solve the problem quickly, but the delivery patterns generated by the two-stage models were more robust than those generated by the general IP model. Numerical test on benchmark problems showed that our approach could generate solutions with the same fleet sizes as in previous studies. Our approach needs to solve much fewer VRPs in the solution process and will be efficient and useful for solving problems with long planning horizon and multiple frequencies.