Back
 AJCM  Vol.9 No.4 , December 2019
On Vehicle Routing Problems (VRP) with a Focus on Multiple Priorities
Abstract: This paper discusses the concept of priorities based on Time and Quantity, which arise on the occasion of vehicle routing. It explains the interconnectivity between the priorities based on Time and Quantity and formulates a dynamic that shows the fusion of Time and Quantity into the Vehicle Routing Problem’s objective function. The paper focuses on the development of an expanded VRP objective function in which the priorities based on Time and Quantities are imbedded thus opens a vista of knowledge, aggregating and modelling the priorities as a mean to reduce transportation costs that lead to an organized and more timely deliveries of goods employing various of today’s proposed logistic systems coupled with widely used positioning systems.

1. Introduction

In the effective and efficient management of the supply chain (see [1] ), it is observed that, the optimal management of transport of consumables and finished products become imperative. The carrying costs associated with transporting the goods have a direct impact on the final cost consumers must pay, which apart from requiring competitive products, also demand that they are generated in environmentally friendly situations. The state of the art of the Vehicle Routing Problem (VRP) is presented in this paper, listing its variants, models and methodologies for solution.

In the past few decades, the VRP and its variants have grown more popular in the academic literature [2]. Yet, the problem’s characteristics and assumptions vary widely from place to place and from person to person. However, few authors have made efforts to classify the existing articles accordingly. Based on an adapted version of the comprehensive taxonomy suggested by [3], we classify and analyze VRPs with Multiple Priorities (VRPMP) in this paper.

The problem of designing and assigning routes for vehicles that should supply different customers with defined locations and specific demands from a single depot is known as the Vehicle Routing Problem. It is the opinion in [4] that, VRPs attract attention from all walks of life owing to the increased interest in various geographical solutions and technologies as well as its usage in solving logistics and transportation problems. The important key to reduction of transportation costs is a better organization of routes through solving a vehicle routing problem. Consider for example, the organization of fleet routes in various distribution areas: delivery of post, delivery to markets, fuel delivery to gasoline stations, etc. so as to save fuel, money and/or time that can be used for servicing new customers. Also, a better organization of routes in business deliveries can affect the ecological system via a reduction of pollution which is an important problem today.

The VRP by [5] is a generic name given to a whole class of problems involving the visiting of “Customers” by “Vehicles”. The VRP appears very frequently in practical situations which are not directly related to the physical delivery of goods but includes the collection of mails from mailboxes, the picking up and returning of children by schools’ buses, house-call tours by a doctor, preventive maintenance inspection tours, the delivery of laundry and a host of others. These are all referred to as VRPs in which the delivery operation may be collection, collection and delivery or exclusively delivery in which the goods and vehicles can take a variety of forms.

In view of the enormous number of practical situations which gave rise to VRPs, it is not surprising to find that a large number of constraints and/or objectives appear in such problems. Here we consider a problem in which a set of geographically dispersed customers with known requirements must be served with a fleet of vehicles stationed at a central facility or depot with the aim to minimize some distribution objective. It is assumed that all vehicle routes must start and finish at the depot, all the vehicles are of the same make and type and all the routes are open to all the vehicles at all hours of the day.

This calls for a basic VRP that can be characterized in what follows as Sections 2 will be devoted to Basic VRP requirements, 3 will focus on Priorities, 4 discusses Basic VRP Objectives and 5 guides to Problem Formulation and Definitions. The main objective is to minimize the total cost of delivery, to maximize the profit while taking into consideration constraints which vary from one case to another and aim at satisfying customers’ requests having in mind the Time and Quantity priorities.

2. The Basic VRP Requirements

Consider the VRP for a given time period, T. Let X = { x i | i = 0 , 1 , 2 , 3 , , N } be the set of N customers with x 0 the depot. Let V = { v k | k = 1 , 2 , 3 , , M } be the set of M homogenous vehicles stationed at the depot, x 0 . By [6], every pair of locations ( i , j ) , where i , j N and i j , is associated with a travel time, t i j , from customer x i to x j and a distance traveled, d ( i , j ) = d i j , that are symmetrical, i.e. t i j = t j i and d i j = d j i . Every customer, x i , has the following basic requirements:

C1: A quantity, q i , of product to be delivered by a vehicle, v k .

C2: The time, t i j , required by the vehicle, v k , to move from the depot or from a previous customer, x i , to visit the next customer, x j , to unload the quantity, q i and to leave for the next customer or return to the depot should all the customers in that route have been serviced or all the quantity have been exhausted.

C3: The priority, δ i , of the customer, x i , to be serviced by the vehicle, v k .

The customers are serviced from only one depot with a homogeneous and limited fleet. The vehicles leave and ultimately return to the depot after the last customer had been serviced. There is a set V of vehicles with identical capacities. The capacity of each vehicle, v k V is represented by Q k .

Much as each customer is having some requirements also, each vehicle, v k , has the following characteristics to be met thus:

V1: A limited working period, T k , of the vehicle, v k , from the starting time, T k s , to the finishing time, T k f .

V2: The fixed cost, C k , of wages to the driver and the loaders attached to each vehicle.

V3: The carrying capacity, Q k , of the vehicle.

On the customers’ requirements and vehicles’ characteristics, the followings are made:

A1: The variable cost, c i j , is given as the cost of the least path from customer x i to customer x j .

A2: The time, t i j , is the corresponding travel time from customer x i to customer x j .

Let R i = { r i ( 1 ) , , r i ( N ) } represent the set of routes for vehicle v k , where r i ( N ) indicates the nth customer visited and N is the number of customers in the route. We also assume that every route terminates at the depot with r i ( N + 1 ) = 0 .

The distance from where the vehicle can pack to unload to the warehouse or store of each customer is equal; hence, the time to unload per item is fixed.

There is a need to discuss the priorities in what follows next to usher us into the VRP objectives and problem formulations.

3. The VRP Priorities

Over the years, it has become clear that, there are various priorities that a customer can place on the supply requirements to be met by the delivery vehicle e.g. Time of delivery, Quantity to be supplied, etc. This work admits only two of such priorities which are: Priority based on Time for the goods to be delivered and Priority based on Quantity of the product to be delivered. A customer can by any means require that one or more of these priorities be met at a particular time.

3.1. Priority Based on Time

One of the well-known priorities placed on VRPs has to do with the Time Windows, where each customer is associated with a time interval (see [7] ), within which, the customer must be visited or serviced. The VRP with Time Priority (VRPTP) is one of the most important extensions of the VRP. In the VRPTP, each customer specifies a time window within which the service must start. The VRPTP can be used to model various real-life applications, such as bus routing planning [8], industrial waste collection [9], home delivery (see [10] and [11] ) and petrol station replenishment [12], bank deliveries, postal deliveries, national franchise, restaurant deliveries, and security patrol services to mention but a few.

An extension of the VRP with Time Priority is such by [13], which considers multiple periods and assumes that each customer is required to be visited based on a given frequency and given feasible combinations of visiting periods. Recent applications include: routing and scheduling of service teams for preventive maintenance of elevators at customer locations [14] and periodic delivery of blood products to hospitals by the Austrian Red Cross [15].

There are basically four sub-divisions of the time windows to be considered. Each customer, x i N , has time windows, t n e < t i < t n l , i.e. an interval ( t n e , t n l ) (see [6], which corresponds, respectively, to the earliest and latest time the vehicle should service the customer x i ). Let t i be the service time at customer x i then, the following scenarios arise:

P T 1 = ( t 1 e , t 1 l ) : This time window indicates that; the vehicle can arrive any time after the earliest, t 1 e , and must leave before the latest time. This means that, the vehicle can arrive at the customer place at any time of the day and depart at any time as long as the delivery is still done within the latest departure time required by the customer. Of all the time windows, ( t 1 e , t 1 l ) is such that gives room for the vehicle to service the customer at any convenient time within the working period, T k .

P T 2 = ( t 2 e , t 2 l ] : Here, it gives room for the vehicle to arrive at the customer’s location any time within the working period but must depart on or before the customer’s latest departure time.

P T 3 = [ t 3 e , t 3 l ) : Here, the vehicle arrives on or after the earliest time and leaves at any time before the latest departure time. It is closed at the earliest time but open at the latest time interval. In this case, should the vehicle arrive ahead of the arrival time, it cannot be allowed to discharge, hence, has to wait till the earliest arrival time.

P T 4 = [ t 4 e , t 4 l ] : A vehicle is allowed to arrive earlier than t 4 e , but it has to wait until t 4 e before it can start serving the customer. Arriving later than t 4 l is not allowed rather the vehicle must leave at most t 4 l . This is a case of restriction at both the arrival and departure time. It gives no room for the vehicle to come at just any time earlier than the earliest time and must depart on or before the latest departure time. Should the vehicle have not even finished discharging; it must leave at the latest departure time to give room for other things as the case may be. This case calls for the unloading time not to be elongated unnecessarily as the customer might have other things to attend to.

From Figure 1, a customer, x i , can only be linked to a time priority only once. Such that:

μ i ( x i ) = P T 1 or P T 2 or P T 3 or P T 4 (3.1)

where μ i of x i represents the priority of a customer.

3.2. Priority Based on Quantity

For priority based on quantity, there are two important cases to be considered here, namely: 1) a situation whereby the demand of a customer may be fulfilled by more than one vehicle. This occurs in situations whereby a customer’s demand exceeds the vehicle capacity, but can also turn out to be cost effective on the side of the supplier in that, the vehicle goes directly to the customer; and 2), is when a customer requires a quantity that is within the carrying capacity of the vehicle. Hence, servicing customers on that route and meeting the specified quantities without a tradeoff. Each customer, x i , has a quantity demanded, i.e. an interval [ q n min , q n max ] , which corresponds, respectively, to the minimum and maximum quantities demanded by the customer, x i (see [6] ).

Variations on priority based on quantity are thus:

P Q 1 = ( q 1 min , q 1 max ) : This expression indicates that, the minimum and maximum quantity that the customer requires are open at both ends meaning that, the customer has got no specific quantity to be delivered. Hence, the vehicle can deliver any amount of the product to the customer as long as it is still within the capacity of the vehicle. The flexibility of this case makes planning on quantity to be delivered to each customer difficult for the vehicle from on set.

P Q 2 = ( q 2 min , q 2 max ] : Here, the customer has an upper limit of quantity required to be supplied. The quantity is open at only the lower end and closed at the other end. There is a definite quantity that the customer is looking forward to receiving but gives rooms for supply of less.

Figure 1. Time priorities tree.

P Q 3 = [ q 3 min , q 3 max ) : Here, the quantity that will be supplied to the customer cannot be less than a particular amount but, can be more should the vehicle can be able to deliver it. In practice, this allows the customers to place more order at the point of delivery for a quantity higher than what has been requested for earlier. This could cause the vehicle not being able to service all the customers that has been marked for servicing that day.

P Q 4 = [ q 4 min , q 4 max ] : This is a case where by the customer has a range of quantities to be delivered. It gives no room for the customer to demand more than what has earlier been demanded. It is strictly bounded below and above. In practical terms, there are situations a customer might need more of the quantities due to pressing demand not envisaged due to patronage. Such priority does not give room for variation on the part of the customer even if it is at a disadvantage. It must be noted that, in practice, situations whereby the interval is locked at both ends, not flexible enough, is not an ideal priority as it gives no room for future expansion.

It must be noted that, every customer is bound to have priorities based on time as well as based on quantity. Also, each customer must fulfil only one such priority condition. In that regard, since only one set of such time and quantity priority conditions may be fulfilled by a customer, it then leads to the following priority formulations.

Figure 2 shows the interconnectivity between the Time and Quantity Priorities. From the priority formulation tree, Figure 2, when a customer, x i , is not serviced, the Time Priority of the customer, P T n = 0 . where 1 n 4 . In the same vein, if a customer, x i , is not serviced then, P Q n = 0 else, P T n = 1 and P Q n = q n . The customer fulfils only a time priority and only one quantity priority condition at a time. With this, the sum of the time and quantity priorities for each of the customers from Figure 2 is given by:

μ i ( x i ) = [ P T 1 ( P Q 1 ) or P T 1 ( P Q 2 ) or P T 1 ( P Q 3 ) or P T 1 ( P Q 4 ) ] [ P T 2 ( P Q 1 ) or P T 2 ( P Q 2 ) or P T 2 ( P Q 3 ) or P T 2 ( P Q 4 ) ] [ P T 3 ( P Q 1 ) or P T 3 ( P Q 2 ) or P T 3 ( P Q 3 ) or P T 3 ( P Q 4 ) ] [ P T 4 ( P Q 1 ) or P T 4 ( P Q 2 ) or P T 4 ( P Q 3 ) or P T 4 ( P Q 4 ) ] (3.2)

while the sum of the priorities made by all the customers is given as:

i = 1 N δ i ( x i ) = i = 1 N μ i ( x i ) n = 1 4 P T n { n = 1 4 P Q n } (3.3)

It implies that, when a customer chooses a particular time priority, the other time priorities that are not chosen is set as zero. Also, whichever time priority a customer has chosen eventually is linked to the desired quantity priority the customer requires. Hence, when a particular quantity priority is chosen, the other three quantity priorities not chosen are set as zero. Leaving us with a particular time priority linked to a particular quantity priority.

The next section will dwell on the objective function and the inclusion of the priority into the objective formulation.

Figure 2. Priorities formulation tree.

4. Basic VRP Objectives

Though, the main objective of the VRP is to design routes for vehicles to supply customers so as to minimize the overhead cost, there are however several inherent objectives of the VRPs which include:

O1: Maximize the sum of the priorities of customers that can be supplied by the set V of vehicles.

O2: Minimize the fixed cost of vehicles used in the routing process.

O3: Minimize the total variable cost of the routes.

Obviously, objectives O2 and O3 above cannot be stated in isolation since the value of the optimum solutions is then zero, but must be stated in conjunction with objective O1 (See [5] ).We will use the notation Ox(Oy(Oz)) to imply: apply objective Oz; if more than one optimum solution of Oz exists, apply objective Oy; if more than one optimum solution to objective Oz and Oy still exist, apply to them objective Ox. All objectives normally used in practice and found in the literature can be represented in this way. For instance:

1) Minimize total cost of vehicles used assuming all customers must be routed.

This implies that, the sum of all the priorities, i = 1 N δ i = L , of the customers, x i ,

that can be supplied by the set V of the vehicle with C k the fixed cost of vehicle k hence, the objective; minimize total cost of vehicles is given as:

Min J = O 2 ( O 1 ) (4.1)

2) Minimize total route distance or time travelled assuming all customers

must be routed. This implies that, the sum of all the priorities, i = 1 N δ i = L , of

the customers, x i , that can be supplied by the set V of vehicles with c i j the distance or time from x i to x j of vehicle k. Hence, the objective Minimize total route distance or time is:

Min J = O 3 ( O 1 ) (4.2)

3) Minimize total cost of vehicles used assuming all customers must be routed and using this number of vehicles minimize the distance travelled. This implies

that, the sum of all the priorities, i = 1 4 δ i = L , for all i, that can be supplied by

the set V of the vehicle with C k the fixed cost of vehicle, C k = l < L , with the set c i j < l , the distance or time from x i to x j for all vehicle k. Hence, the objective Minimize total number of vehicles and distance travelled is:

Min J = O 3 ( O 2 ( O 1 ) ) (4.3)

Generally, it has become clear that at every point in time no single objective is determined rather, two or more objectives are aimed to be determined.

5. Problem Formulation and Definitions

Let ξ i j k = 1 if vehicle v k visits customer x j immediately after visiting customer x i otherwise ξ i j k = 0 .

The VRP with Multiple Priorities is a multi-objectives problem with the series, Min k 3 J k . Where Min J 1 , is meant to calculate the least path or distance carrying cost, Min J 2 is aimed at computing the fixed cost and Min J 3 is targeted at evaluating the priorities with:

Min J 1 = α i = 0 N j = 0 N ( c i j k = 1 M ξ i j k ) (5.1)

Min J 2 = β k = 1 M ( C k j = 1 N ξ 0 j k ) (5.2)

Min J 3 = γ j = 1 N ( δ j i = 0 N k = 1 M ξ i j k ) (5.3)

where α , β and γ by [5] are constants for weighting the terms corresponding to each objective.

On combining all the three sub objectives (5.1), (5.2) and (5.3) we obtain:

Min J = Min J 1 + Min J 2 + Min J 3 (5.4)

Min J = α i = 0 N j = 0 N ( c i j k = 1 M ξ i j k ) + β k = 1 M ( C k j = 1 N ξ 0 j k ) + γ j = 1 N ( δ i i = 0 N k = 1 M ξ i j k ) (5.5)

Subject to

i = 0 N k = 1 M ξ i j k 1 , j = 1 , , N ; k = 1 , , M (5.6)

i = 0 N ξ i p k j = 0 N ξ p j k = 0 , p = 0 , , N (5.7)

i = 1 N ( q i j = 0 N ξ i j k ) C k , k = 1 , (5.8)

i = 0 N j = 0 N t i j ξ i j k + i = 1 N ( u i j = 0 N ξ i j k ) T k f T k s (5.9)

j = 1 N ξ 0 j k 1 (5.10)

y i y j + N k = 1 M ξ i j k N 1 , i j = 1 , , N (5.11)

ξ i j k { 0 , 1 } , i , j , k (5.12)

The constraint (5.6) states that a customer can be visited at most once. Constraint (5.7) states that if a vehicle visits a customer, it must also depart from it. Constraint (5.8) is the capacity of the vehicle on each route. Constraint (5.9) is the working time limitations on each route. Constraint (5.10) states that a vehicle must be used at most once. Where y i is arbitrary, the relation (5.11) is the sub-tour-elimination condition derived for the Travelling Salesman Problem (TSP) by [16] and VRP as opined by [17] and [18]. This forces each route to pass through the depot. Constraint (5.12) is the integrality condition.

If the aim of the VRP is to determine priority alone then, the first series, (5.1) and second series of (5.2) is set as zero while if the objective is to determine the priority as well as the cost alone then, the second series, (5.2) is set as zero. But where all the objectives are to be computed then, (5.5) holds.

The central ideal behind the introduction of priorities to VRPs is to help to plan ahead of time which customer gets a particular quantity and at what time, to enable timely delivery, manage the space and capacity of the vehicle and ensure that all the customers are serviced depending on the priorities and minimize both the fixed and variable cost with a view to maximize the profit.

Cite this paper: Adebayo, K. , Aderibigbe, F. and Dele-Rotimi, A. (2019) On Vehicle Routing Problems (VRP) with a Focus on Multiple Priorities. American Journal of Computational Mathematics, 9, 348-357. doi: 10.4236/ajcm.2019.94025.
References

[1]   Eliana, M.T., Antonio, H., Escobar, Z. and Mauricio, G.E. (2015) Literature Review on the Vehicle Routing Problem in the Green Transportation Context.

[2]   Nathalie, D.J., Mieke, D. and Inneke, V.N. (2006) The Vehicle Routing Problem: State of the Art Classification and Review. Research Center for Operations Management, Department of Decision Sciences and information Management, Faculty of Economics and Business, KU Leuven, Belgium.

[3]   Larsen, J. (2004) Refinements of the Column Generation Process for the Vehicle Routing Problem with Time Windows. Journal of Systems Science and Systems Engineering, 13, 326-341.
https://doi.org/10.1007/s11518-006-0168-9

[4]   Gintaras, V. (2014) Genetic Algorithm for Vehicle Routing Problem. Doctoral Dissertation, Technological Sciences, Informatics Engineering (07 T).

[5]   Christofides, N., Mingozzi, A. and Toth, P. (1976) Combinatorial Optimization. John Wiley & Sons, Hoboken.

[6]   Russell, R.A. and Chiang, W.C. (2006) Scatter Search for the Vehicle Routing Problem with Time Windows. European Journal of Operational Research, 169, 606-622.
https://doi.org/10.1016/j.ejor.2004.08.018

[7]   Wen, M. (2010) Rich Vehicle Routing Problems and Applications. PhD Thesis, DTU Management, Lyngby, No. 8.

[8]   Fuegenschuh, A. (2009) Solving a School Bus Scheduling Problem with Integer Programming. European Journal of Operational Research, 193, 867-884.
https://doi.org/10.1016/j.ejor.2007.10.055

[9]   Kim, B., Kim, S. and Sahoo, S. (2006) Waste Collection Vehicle Routing Problem with Time Windows. Computers & Operations Research, 33, 3624-3642.
https://doi.org/10.1016/j.cor.2005.02.045

[10]   Weigel, D. and Cao, B. (1999) Applying GIS and OR Techniques to Solve Sears Technician-Dispatching and Home Delivery Problems. Interfaces, 29, 112-130.
https://doi.org/10.1287/inte.29.1.112

[11]   Braysy, O., Nakari, P., Dullaert, W. and Neittaanmaki, P. (2009) An Optimization Approach for Communal Home Meal Delivery Service: A Case Study. Journal of Computational and Applied Mathematics, 232, 46-53.
https://doi.org/10.1016/j.cam.2008.10.038

[12]   Cornillier, F., Laporte, G., Boctor, F.F. and Renaud, J. (2009) The Petrol Station Replenishment Problem with Time Windows. Computers & Operations Research, 36, 919-935.
https://doi.org/10.1016/j.cor.2007.11.007

[13]   Beltrami, E.J. and Bodin, L.D. (1974) Networks and Vehicle Routing for Municipal Waste Collection. Networks, 4, 65-94.
https://doi.org/10.1002/net.3230040106

[14]   Blakeley, F., Bozkaya, B., Cao, B., Hall, W. and Knolmajer, J. (2003) Optimizing Periodic Maintenance Operations for Schindler Elevator Corporation. Interfaces, 33, 67-79.
https://doi.org/10.1287/inte.33.1.67.12722

[15]   Hemmelmayr, V., Doerner, K.F., Hartl, R.F. and Savelsbergh, M.W.P. (2009) Delivery Strategies for Blood Products Supplies. OR Spectrum, 31, 707-725.
https://doi.org/10.1007/s00291-008-0134-7

[16]   Miller, D.L. and Pekny, J.F. (1995) A Staged Primal-Dual Algorithm for Perfect B-Matching with Edge Capacities. ORSA Journal on Computing, 7, 298-320.
https://doi.org/10.1287/ijoc.7.3.298

[17]   Kohl, N., Desrosiers, J., Madsen, O.B.G., Solomon, M.M. and Soumis, F. (1999) 2-Path Cuts for the Vehicle Routing Problem with Time Windows. Transportation Science, 33, 101-116.
https://doi.org/10.1287/trsc.33.1.101

[18]   Jean-Francois, C., Gilbert, L., Martin, W.P.S. and Daniele, V. (2007) Vehicle Routing. In: Handbook on OR and MS, Elsevier, Amsterdam, Vol. 14, 367-427.

 
 
Top