A Combined Approach for Solving Periodic Vehicle Routing Problem with Fleet and Driver Scheduling

A Combined Approach for Solving Periodic Vehicle Routing Problem with Fleet and Driver Scheduling

Suwarno Ariswoyo, Herman Mawengkang

Department of Mathematics, University of Sumatera Utara

This paper develops a model for the optimal management of periodic deliveries of a given commodity called Periodic Vehicle Routing Problem (PVRP). The goal is to schedule the deliveries according to feasible combinations of delivery days and to determine the scheduling of fleet and driver and routing policies of the vehicles. The objective is to minimize the sum of the costs of all routes over the planning horizon. We propose a combined approach of heuristic algorithm and exact method to solve the problem.

Keywords: Vehicle routing problem, scheduling, combined approach

1. Introduction

   In the distribution of goods or services, there exists a problem that is known as the vehicle routing problem. In fact there is a wide variety of situations and therefore the problem is not unique but a vast class of problems, each one with its own characteristics and constraints. Vehicle Routing Problem is one of the important issues that exist in transportation system. Many researchers have been working in this area to discover new methodologies in selecting the best routes in order to find the better solutions.

   The vehicle routing problem (VRP) can be defined as follows: vehicles with a fixed capacity Q must deliver order quantities qi ( i 1,, n ) of goods to n customers from a single depot (i = 0). Knowing the distance dij between customers i and j ( i, j 1,, n ), the objective of the problem is to minimize the total distance traveled by the vehicles in a way that only one vehicle handles the deliveries for a given customer and the total quantity of goods that a single vehicle delivers is not larger than Q [1].

   In PVRP, Each customer i I 1, 2,,i,, n

   specifies a set k i of combinations, and the visit days

   combinations. Thus, the vehicles must visit the customer i

   on the days belonging to the selected combination.

   Early formulations of the PVRP were developed by Beltrami and Bodin [2] and by Russell and Igo [11] who proposed heuristics applied to waste collection problems. Tan and Beasley [14] use the idea of the generalized assignment method proposed by Fisher and Jaikumar [9] and assign a visiting schedule to each vertex. Eventually a heuristic for the VRP is applied to each day. Russell and Gribbin [12] developed a heuristic organized in four phases. Solution methods in these papers have focused on two-stage (construction and improvement) heuristics. Cordeau et al. [6] present another algorithm: The solution algorithm is a TS heuristic which, differently from the above heuristics, may allow infeasible solutions during the search process. Similarly, good results were obtained in the more recent work of Ha. Dji constantinuo and Baldacci [8], Angelelli and Speranza [1], and Blakeley et al. [3] who provide specific practical applications of the PRVP.

   Francis et al. [10] introduce the Periodic Vehicle Routing Problem with Service Choice (PVRP-SC) which allows service levels to be determined endogenously. The PVRP-SC is dened as follows:

   Given: A set of nodes with known demand and minimum visit frequency requiring service over the planning period; aeet of capacitated vehicles; a set of service schedules with headways and service benets; and a network with travel times.

   Find: An assignment of nodes to service schedules and a set of vehicle routes for each day of the planning period with the objective

   Minimize: the total routing cost incurred net of the service benet accrued.

   Francis et al. [10] develop an integer programming formulation of the PVRP-SC with exact and heuristic solution methods. Due to the computational complexity of the problem, solutions to the discrete PVRP-SC are limited by instance size. Continuous approximation models are better suited for large problem instances, yet the use of continuous approximation models for periodic routing problems has been limited.

   are assigned to the customer by selecting one of these

   Daganzo [7] presents modeling techniques for distribution problems with varying service requirements. Smilowitz and Daganzo [13] develop continuous

   approximation models for distribution network design with multiple service levels. These references show that

   nodes, A i, j : i, j N0. Each customer node i N has a known daily demand, , and a minimum service frequency, , measured in days per period. The

   demand accumulated between visits, , is a function of

   continuous approximations can be powerful tools for

   the schedule

   and the daily demand of the node. The

   strategic and tactical decisions when service choice exists. In continuous approximation models, aggregated data are used instead of more detailed inputs.

   This paper concerns with PVRP with fleet and driver scheduling (PVRFDSP). The basic framework of the vehicle routing part can be viewed as a Heterogeneous Vehicle Routing Problem with Time Windows (HVRPTW) in which a limited number of heterogeneous vehicles, characterized by different capacities are available and the customers have a specified time

   windows for services. We propose a mixed integer

   stopping time at a node, , is a function of the frequency of the schedule since more items accumulate with less frequent service and, therefore, require more time to load/unload. Associated with each arc i, j A is a

   known travel cost, cij . There is a set K of vehicles, each with capacity C. The following allocation and routing variables dene the solution to the discrete formulation.

   = 1 if node is visited by vehicle on schedule

   programming formulation to model the problem. A

   0 otherwise

   feasible neighbourhood heuristic search is addressed to

   = 1 if vehicle travels the arc (, ) on day

   get the integer feasible solution after solving the continuous model of the problem.

   0 otherwise

   Section 2 reviews the integer programming formulation of the PVRP with Service Choice from Francis et al. [10]. Section 3 describes the mathematics formulation of the (PVRFDSP). Feasible neighbourhood heuristic search is given in Section 4. The conclusions are described in Section 5.

   The discrete formulation for PVR-SC developed in Francis et al. [10] is:

   = min (, ) +

   ( ) (1)

2. Models Of The PVRP- SC

   In this section, we present the discrete formulations of

   Subject to

   (2)

   the PVRP-SC from Francis et al. [10]. In the PVRP-SC, customers are visited a preset number of times over the period with a schedule that is chosen from a menu of schedule options. Let S denote this menu of schedules, and T denote the set of days in the period. The parameter

   1

   (3)

   , (4)

   a links schedules to days, where if a 1

   day

   =

   ,

   sd sd

   0

   d T

   is in schedule s S

   and

   asd 0

   otherwise.

   , (5)

   Each schedule has an associated visit frequency

   =

   0,

   measured by number of days in the schedule: =

   0

   0 /p>

   . For given schedule option, the headway

   , (6)

   between visits is dened in terms of the visit frequency as

   H s 1 s . Each schedule has an associated benet

   1

   , , (7)

   related to the cost benet of more frequent service which is assumed to be stationary over the time period.

   2.1Discrete Formulation Of The PVRP-SC

   The discrete formulation of the PVRP-SC is dened for a set of nodes, 0, which consists of customers nodes, N, and a depot, i 0 , and a set of arcs connecting

   0, 1 , , (8)

   0, 1 (, ) , , (9) The objective function (1) balances arc travel times,

   stopping times and demand weighted service benet.

   Constraints (2) enforce the minimum frequency of visits for each node. Constraints (3) ensure that one schedule and one vehicle are chosen for each demand node. Constraints (4) represent vehicle capacity constraints. Constraints (5) link the x and y variables for the demand

   nodes. Constraints (6) ensure ow conservation at each node. Constraints (7) are the subtour elimination constraints and ensure that all tours contain a visit to the depot. Constraints (8) and (9) dene the binary variables for allocation and routing, respectively.

3. Mathematical Formulation Of PVRFDSP

   l l

   . We denote the planning horizon by T and the set of drivers by D. The set of workdays for driver l D is denoted by Tl T . The start working time and latest ending time for driver l D on day t T are given by gt and ht , respectively. Let DI and DE denote the set of

   the internal and external drivers ( D DI DE ). For each internal driver l DI , let H denote the maximum weekly working duration. We denote the maximum elapsed driving time without break by F and the duration of a break by G (according to the EU driver legislation).

   Let K denote the set of vehicles. For each vehicle k K , let Qk and Pk denote the capacity in weight and in volume, respectively. We assume the number of vehicles equals to the number of drivers. Denote the set of n customers (/nodes) by N 1, 2,, n. Denote

   t is the elapsed driving time for vehicle k at customer i

   u

   y

   ik

   is

   lk

   after the previous break on day t. Binary variable t

   l

   s

   l

   set to 1 if vehicle k is assigned to driver l on day t. Variables rt and t are the total working duration and the total travel time for driver l on day t, respectively.

   This notations used are given as follows : Set:

   T The set of workdays in the planning horizon,

   DI The set of internal drivers,

   DE The set of external drivers,

   D The set of drivers D = DI DE,

   Tl The set of workdays for driver l D,

   K The set of vehicles,

   N The set of customers,

   N0 The set of customers and depot N0 = {0, n

   + 1} N,

   Ki The set of preferable vehicles for customer

   i N,

   Ti The set of days on which customer i N

   orders,

   Parameter:

   Qk The weight capacity of vehicle k K ,

   the depot by 0, n 1. Each vehicle starts from 0

   and terminates at n 1. Each customer i N

   Pk The volume capacity of vehicle k K ,

   cij The travel time from node i N0 to node

   specifies a set of days to be visited, denoted by Ti T . On each day t Ti , customer i N requests service

   j N0 ,

   [ai, bi] The earliest and the latest visit time at

   node i N0 ,

   i

   p

   d

   i

   with demand of qt in weight and t in volume, service t

   i

   The service time of node i N0

   on day

   i

   duration d t and time window a ,b . Note that, for the

   i i

   t Ti ,

   i i i

   q

   depot i 0, n 1 on day t, we set qt pt dt 0 . t

   i

   Denote the set of preferable vehicles for visiting customer

   p

   i

   i by Ki ( K K ) and the extra service time per pallet by

   t

   e if a customer is not visited by a preferable vehicle. The i

   The weight demand of node i N0 on day t Ti ,

   The volume demand of node i N0 on

   travel time between customer i and j is given by

   cij .

   day t Ti ,

   x

   Denote the cost coefficients of the travel time of the internal drivers by A and the working duration of the external drivers by B.

   e The extra service time per pallet when a non-preferable vehicle is used,

   [ gt , ht ] The start time and the latest ending time of

   We define binary variable

   t ijk

   to be 1 if vehicle k

   l l

   driver l D on day t T ,

   travels from node i to j on day t, binary variable wt i to be 1 if customer i is not visited by a preferred vehicle on day

   H The maximum working duration for each internal driver over the planning horizon,

   ik

   z

   t. Variable vt is the time that vehicle k visits node i on

   1. The maximum elapsed driving time without break,

      day t. Binary variable

      t indicates whether vehicle k

   2. The duration of the break for drivers,

   ik

   takes a break after serving customer i on day t. Variable

   K The cost factor on the total travel time of

   , (14)

   1

   internal drivers,

   0

   +

   1

   K The cost factor on the total working

   2

   Variables:

   duration of the external drivers,

   , 0, , (15)

   1 , ,

   xt Binary variable indicating whether vehicle

   ilk

   k K

   j N

   travels from node on day t T ,

   i N0 to

   , (16)

   + , 0,

   0

   0

   w

   i

   t Binary variable indicating whether

   , (17) i

   customer

   i N0

   is visited by a non-

   + + . . +

   + .

   preferable vehicle on day t T ,

   v

   ik

   t The time at which vehicle k K

   starts

   1 , 0, , (18)

   , , (19)

   service at node i N0 on day t T ,

   ( . ) , (20)

   z

   ik

   t Binary variable indicating whether vehicle

   0

   k K

   takes break after serving node

   ( . )

   , (21)

   +1,

   i N0 on day t T ,

   1

   ik

   ut The elapsed driving time of vehicle

   k K at node i N0 after the previous

   0 0

   , , (22)

   1

   break on day t T ,

   +1,

   y

   lk

   t Binary variable indicating whether vehicle

   , , (23)

   k K

   is assigned to driver l D on day

   (24)

   t T ,

   rt The total working duration of driver

   , , , 0, 1 , 0 , ,

   l

   l D on day t T ,

   , (25)

   st The total travel distance of driver l D

   , , , 0 ,

   , ,

   l

   0

   on day t T .

   The mathematical formulation for this problem is presented as follows:

   min 1 . + 2 . + (10)

   , (26)

   The objective function (10) minimizes weighted sum of the travel time of the internal drivers and the working duration of the external divers over the planning horizon.

   Constraints (11) state that each customer must be

   Subject to:

   = 1

   , (11)

   visited by one vehicle on each of(1i0t)s delivery days. Constraints (12) define whether each customer is visited by a preferable vehicle. Constraints (13-14) guarantee that the vehicle capacities are respected in both weight

   0

   and volume.

   i

   N, t

   Ti (11)

   \

   =

   , (12)

   Constraints (15-16) define the elapsed driving time.

   0

   More specifically, for the vehicle (k) travelling from customer i to j ion Nda,yt t, Tthi e elapse(1d2d) riving time at j

   0

   , (13)

   equals the elapsed driving time at i plus the driving time

   from i to j (i.e., ut ut + cij ) if the vehicle does not

   k jk K, t ik T (13)

   ik

   take a break at customer i (i.e., zt = 0); Otherwise, if the

   z

   ik

   vehicle takes a break at customer i (i.e., t = 1), the

   elapsed driving time at j will be constrained by (10) which make sure it is greater than or equal to the travel

   u

   z

   jk

   ik

   time between i and j (i.e., t cij). Constraints (17) guarantee that the elapsed driving time never exceeds an upper limit F by imposing a break at customer i (i.e., t

   = 1) if driving from customer i to its successor results in a

   elapsed driving time greater than F.

   Constraints (18) determine the time to start the service at each customer. If j is visited immediately after i, the

   Step 2 : Obtain a (sub-optimal) integer feasible solution, using heuristic rounding of the continuous solution.

   Step 3 : Divide the set I of integer variables into the set I1 at their bounds that were nonbasic at the continuous solution and the set I2, I = I1+ I2.

   Step 4 : Perform a search on the objective function, maintaining the variables in I1 nonbasic and allowing only discrete changes in the values of the variables in I2.

   Step 5 : At the solution obtained in step 4, examine the reduced costs of the variables in I1. If any should be released from their bounds, add them to set I2 and repeat from step 4, otherwise

   jk

   time vt

   to start the service at j should be greater than or

   terminate.

   v

   ik

   equal to the service starting time t at i plus its service

   The above summary provides a framework for the

   i

   duration d t , the extra service time

   e pt

   if i is visited

   development of specific strategies for particular classes of problems. For example, the heuristic rounding in step

   i

   j

   z

   ik

   by an inappropriate vehicle (i.e., wt = 1), the travel time between the two customers cij , and the break time G if the driver takes a break after serving I (i.e., t = 1).

   Constraints (19) make sure the services start within the customers time window.

   Constraints (20-21) ensure that the starting time and ending time of each route must lie between the start working time and latest ending time of the assigned driver. Constraints (22) calculate the total travel time for each internal driver. Constraints (23) define the working duration for each driver on every workday, which equals the time the driver returns to the depot minus the time he/she starts work. Constraints (24) make sure that the internal drivers work for no more than a maximum weekly working duration, referred to as 37 week-hour constraints. Constraints (25-26) define the binary and positive variables used in this formulation. The overall model should contain constraints (2-7) from PVRP-SC.

4. Feasible Neighborgood Heuristic Search

   While a straightforward brand-and-bound approach could be adopted, for many classes of large-scale problems such a procedure would be prohibitively expensive in terms of total computing time. We have adopted the approach of examining a reduced problem in which most of the integer variables are held constant and only a small subset allowed varying in discrete steps.

   This may be implemented within the structure of a program by marking all integer variables at their bounds at the continuous solution as nonbasic and solving a reduced problem with these maintained as nonbasic.

   The procedure may be summarized as follows:

   Step 1 : Solve the problem ignoring integrality requirements.

   2 can be adapted to suit the nature of the constraints, and step 5 may involve adding just one variable at a time to the set I2.

   At a practical level, implementation of the procedure requires the choice of some level of tolerance on the bounds on the variables and also their integer infeasibility. The search in step 4 is affected by such considerations, as a discrete step in a super basic integer variable may only occur if all of the basic integers remain within the specified tolerance of integer feasibility.

   In general, unless the structure of the constraints maintains integer feasibility in the integer basic variables for discrete changes in the superbasic, the integers in the set I2 must be made superbasic. This can always be achieved since it is assumed that a full set of slack variables is included in the problem.

5. Conclusions

   This paper was intended to present a solution for one of the most important problems in Supply Chain Management, Distribution problems. The aim of this paper was to develop a model of Periodic vehicle Routing with Fleet and Driver Scheduling Problems This problem has additional constraint which is the limitation in the number of vehicles. The proposed algorithm employs nearest neighbor heuristic algorithm for solving the model. This algorithm offers appropriate solutions in a very small amount of time.

6. References

1. Angelelli. E., & Speranza. M.G. 2002. The periodic vehicle routing problem with intermediate facilities. European Journal of Operational Research 137, 2, 233 247.

2. Beltrami, E., Bodin, L., 1974. Networks and vehicle routing for municipal waste collection. Networks 4(1), 6594.

3. Blakely, F., Bozkaya, B., Cao, B., Hall, W., Knolmajer, J., 2003. Optimizing periodic maintenance operations for Schindler Elevator Corporation. Interfaces 33(1), 6779.

4. Chao, I.M., Golden, B., Wasil, E., 1995. An improved heuristic for the period vehicle routing problem. Networks 26(1), 2544.

5. Christodes, N., Beasley, J., 1984. The period routing problem. Networks 14(2), 237256.

6. Cordeau, J.F., Gendreau, M., Laporte, G., 1997. A Tabu Search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2), 105119.

7. Daganzo, C. F., 1987. Modeling distribution problems with time windows: Part II. Transportation Science 21(3), 180187.

8. Dji constantinuo. Ha, & Baldacci. E. 1998. A multi-depot period vehicle routing problem arising in the utilities sector. Journal of Operations Research Society, 49, 12, 12391248.

9. Fisher. M.L., & Jaikumar. R. 1981. A generalized assignment heuristic for vehicle routing. Networks,11, 109±124.

10. Francis, P., Smilowitz, K., Tzur, M., 2004. The period vehicle routing problem with service choice.Transportation Science.

11. Russell, R., Igo, W., 1979. An assignment routing problem. Networks 9(1), 117.

12. Russell. R.A., & Gribbin. D. 1991. A multiphase approach to the period routing problem. Networks, 21, 747±765

13. Smilowitz, K., Daganzo, C. F., 2004. Cost modeling and solution techniques for complex transportation systems. IEMS Working paper 04-006, Northwestern University.

14. Tan. C.C.R., & Beasley. J.E. 1984. A heuristic algorithm for the period vehicle routing problem. OMEGA, Internaional Journal of Management Science, 12, 5, 497±504.