A Bi-objective VRPTW Model for Non-adjacent Products
Mohammad Hossein Sarbaghi Yazdi, Farhad Esmaeili
Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran
Email address:
To cite this article:
Mohammad Hossein Sarbaghi Yazdi, Farhad Esmaeili. A Bi-objective VRPTW Model for Non-adjacent Products. American Journal of Science, Engineering and Technology. Vol. 2, No. 1, 2017, pp. 1-5. doi: 10.11648/j.ajset.20170201.11
Received: October 30, 2016; Accepted: December 26, 2016; Published: January 12, 2017
Abstract: Vehicle Routing Problem (VRP) with time windows is a generalization of the classic VRP. Specifically, every customer must be met in a certain time window. Sometimes in the real life, it is not possible to carry different products simultaneously. In other words, these products are non-adjacent. This paper presents a comprehensive model for the vehicle routing problem with time windows and the possibility of delivery split of non-adjacent products. The proposed model is an extension of VRP considering the profit in a bi-objective optimization model.
Keywords: VRP, Time Window, Bi-objective, Non-adjacent Products
1. Introduction
Today, transportation planning is one of the important fields in operations research, industrial engineering, and civil engineering. The main objective of this field is to minimize the cost of transportation of goods and materials from the producers to the consumers.
1.1. Vehicle Routing Problem
VRP is one of the important problems has been raised in the field of logistics management and transportation systems. VRP is a generalization of traveling salesman problem (TSP), which is considered as a vehicle. VRP is aimed at determining the optimum route of the vehicle so that to meet the demands of all customers where all constraints are satisfied and transportation cost is minimized. In classic VRP, the start and the end of all routes is a specific warehouse or a central depot.
The VRP is generally defined on a complete graph G=(V, A, D). Where V={V_{0}, V_{1}, V_{2}, …, V_{n}} is the set of nodes (vertices) and A={(V_{i}, V_{j}): i≠j} is set of arcs that connect node i to j. V_{0} indicates central depot and V_{n} represents the customer n. d_{ij} represents distance or cost between node i and node j. q_{i} is demand in node i. Typically, the objective is to minimize the total travel cost.
Dantzig and Ramser [1] proposed the VRP for the first time. After that, many variants of VRP have been considered: VRP with time windows (VRPTW), pickup and delivery (VRPPD), multi depot VRP (MDVRP), and so on.
1.2. Vehicle Routing Problem with Time Window
If each customer must be visited during a specific time window, we face with VRPTW. In fact, time window is a time interval with earliest time (b_{i}) and the latest time (e_{i}) that a customer permits to start receiving service. Some of applications of the VRPTW include postal deliveries, refuse collection, bank deliveries, school bus routing, etc.
Over the past 25 years, many researchers have worked on VRP with time windows. VRPTW belongs to NP-Hard problem [2], the same as the classic VRP, so many meta-heuristics have been used to solve it, e.g. Simulated Annealing (SA) [3, 4], Genetic Algorithms (GA) [5, 6], Tabu Search (TS) [7, 8] and Ant colony Optimization (ACO) [9]. Some authors like Yu et al. [10] presented a hybrid approach to solve VRPTW, a mixture of ACO and TS. Küçükoglu and Öztürk [11] presented a hybrid algorithm which includes tabu search and simulated annealing.
In the last three decades, researchers have mixed VRPTW with other modes that are close to real-word problems, for instance VRPTW with Split Delivery (VRPTWSD) [12, 13]. Dror and Trudeau [14] presented split delivery problem for the first time. In VRPSD, unlike the classic VRP, more than one vehicle can supply demand of each node [15]. El-Sherbeny [16] has reviewed literatures in VRPTW and its combination to other VRP modes. He studied various methods of solving VRPTW.
1.3. Vehicle Routing Problem with Profit
In classic VRP and TSP each node should meet once and it will fulfill the demand of all nodes, but in TSP with profit (TSPP) and VRP with profit (VRPP), there is not any obligation to serve all nodes and customers are served in accordance with the profit of meeting. In this problem, each node gets a reward after meeting and a trade-off between cost and profit in each node will indicate which nodes must been met [17]. In TSPP and VRPP there are two objectives having obviously conflict:
• Maximizing profit through meeting the maximum number of customers, which cause increase in distances and travel costs.
• Minimizing travel distances that cause decrease in profit of customer’s meeting.
If two objectives were homogenous, for example both be currency, we can solve them via converting to the single-objective problem. As keller and Goodchild [18] mentioned, in many cases these two objectives are not commensurable and we should consider them as a bi-objective problem.
Feillet et al. [19] describe three classes of single-objective problems that have proposed in TSPP:
• PTP (Profitable Tour Problem): their objective function is a combination of two objectives, i.e. minimizing travel cost minus profit of customers’ meeting [17].
• OP (Orienteering Problem) or STSP (Selective TSP): their objective function is maximizing collected profit such that travel costs do not exceed a predetermined value C_{max} [20].
• QTSP (Quota TSP) or PCTSP (Prize Collecting TSP): their objective function is minimizing the total traveling distance such that profit of customers’ meeting which should not be less than a fixed amount of P_{min} [21, 22].
It seems that VRPP has been less considered in the literature of VRP [23]. Team OP (or TOP) is an extension of OP that has been studied by Chao et al. [24]. They presented a five-steps metaheuristic approach based on simulated annealing to solve this problem. Lin and Yu [25] used a simulated annealing heuristic for TOP. Boussier et al. [26] used an exact method to solve this problem. Aráoz et al. [27] solved a Prize Collecting Rural Postman in which the objective is minimizing the residuum of collected profit and traveling costs.
2. Proposed Model
This paper presents a bi-objective model for VRP with time windows and split deliveries. The considered objectives are:
• To maximize the profit of customers’ meeting: it considers specific profit for each unit of product which has been met.
• To minimize the costs, e.g. traveling cost, waiting time cost, or vehicle cost.
In fact, presented model is a kind of developed VRPP.
As mentioned before, the considered two objectives are not homogenous. In real life, various routes are not the same in view of transportation complexity. For instance, distance between customers 2 and 8 is similar to distance between costumers 4 and 6, but traveling time of these two routes are not the same due to their path conditions, like speed constraint, traffic, etc. Therefore, for each arc between two nodes we consider a difficulty factor and a rest time depending on the traveling time. The time that each vehicle services a node depends on type and amount of its demand.
2.1. Assumptions and Characteristics of Model
• All vehicles start from central depot and traverse a subset of customers in a specified sequence. Then they return to the central depot.
• Each vehicle meets a customer for once.
• Delivery split is possible so that demand of each customer (node) can be met by several vehicles.
• Each customer has a time window to receive services.
• If the vehicle arrives earlier than the lower bound of time window, it should wait until starting of service time.
• A penalty is considered for vehicle tardiness in each node.
• The number of available vehicles is given and vehicle costs are assumed to be zero if they are not in use.
• The time that each vehicle serves a node (customer) depends on type and amount of demand which is met by the vehicle.
• All vehicles have a constant speed and fixed cost per distance (kilometer or mile).
• Difficulty factor of route is defined between 1 and 3.
• The proposed model is designed for non-adjacent products and each customer has determined demand.
• Each vehicle transports only predetermined product and it does not allow transporting any other product.
• A defined award is considered for every unit of customer’s demand which has been met.
• It is not obligatory to meet all the demands.
• Each vehicle should rest when it receives to a node and the rest time depends on distance passed from the previous node to the current one.
2.2. Notations
The notation we used in our model is presented below:
Sets:
Q= {1, 2,…, i, …., N} demanding nodes (points) where point 1 denotes central depot.
arcs or connection between nodes
V= {1, 2, …, v, …., U} vehicles
K= {1, 2, …, r, …., O} products
Parameters:
P_{ir} Profit of r-type product in node i
TC Traveling cost
d_{ij} Length of arc A where , and
b_{ij} Difficulty factor for route i→j, so that b_{ij}=b_{ji}
t_{ij} Traveling time of arc A where
pe_{i} Penalty for tardiness per each unit of time in node i
a_{rv} Binary variable which is equal to 1 if vehicle v is allowed to transport r-type product, and 0 otherwise.
q_{ir} Demand of node of i for product of type r.
g_{r} Necessary time to serve each product of type r.
e Rest time that depends on passed distance
lb_{i} Earliest possible time to start traveling from node i (lower bound of time window)
ub_{i} Latest possible time to arrive in node i (upper bound of time window)
R Fixed cost of using each vehicle
V_{e} Average speed of each vehicle
M An enough huge number (M>>∞)
Decision variables:
x_{ijv} Binary variable which is equal to 1 if vehicle v goes from node i to j, 0 otherwise.
f_{irv} Shortage of demand of r-type product in node i that will be met by vehicle v.
w_{iv} Waiting time of vehicle v in node i
h_{iv} The time that vehicle v spends to serve in node i
re_{iv} The time that vehicle v rests in node i
s_{iv} The time that vehicle v start to serve in node i
2.3. Mathematical Model
The proposed mathematical model is a bi-objective optimization model represented by equations (1)-(15).
The first objective function maximizes the profit of meeting of nodes (customers):
(1)
The second objective function minimizes sum of three elements: 1) total passed distance, 2) fixed cost of using vehicles, and 3) total tardiness penalties in nodes:
(2)
Equation (3) expresses each vehicle cannot visit a node more than once.
(3)
Equation (4) guaranties each vehicle exit after arriving in a node.
(4)
Equation (5) assures if vehicle v supplies a portion of demand of type r in node i, it definitely will meet node i.
(5)
The following equation shows vehicle v can supply demand of type r in node i.
(6)
Each vehicle cannot serve more than its capacity:
(7)
The following equation calculates the time which vehicle v serves node i.
(8)
Equation (9) calculates the rest time of vehicle v in node j
(9)
The necessary time to traverse the arc of is calculates by equation (10).
(10)
Equations (11)-(13) are related to time window. Moreover, equations (11) and (12) prevent forming any subset tours.
(11)
(12)
(13)
Equations (14) and (15) declare the variable types and their signs.
(14)
(15)
3. Solving the Proposed Model with Augmecon Approach
A brief explanation of AUGMECON approach is presented here, an augmented version of the -constraint method.
First, consider the following multi-objective problem:
(16)
Where S is the feasible region. In the -constraint method, one of the objective functions gets optimized while other objective functions are considered as constraints:
(17)
We obtain different solution via changing the value of e_{i}.
In AUGMECON, a developed version of -constraint method, lexicographic optimization is used to determine e_{i}. After calculation of e_{i}, difference between upper and lower bound is divided into several parts. The calculated values indicate allowable e_{i}. Pareto-optimal solutions increase as the number of iterations increases. Then, the below function is solved using obtained values of e_{i}.
(18)
Where S_{i} are slack variables and eps is a very small number (roughly between 10-3 and 10-6). For more information about AUGMECON approach we refer the interested readers to [28] and [29].
4. Computational Results
We used GAMS software to solve the presented model for 8 different randomly-generated instances. The results are shown in table 1.
Instance | Instance characteristics | Number of points on the Pareto-optimal frontier | Computational time (seconds) | |
Number of nodes | Number of product types | |||
1 | 4 | 2 | 10 | 111 |
2 | 4 | 3 | 10 | 244 |
3 | 5 | 2 | 10 | 412 |
4 | 5 | 3 | 10 | 921 |
5 | 6 | 2 | 55 | 1090 |
6 | 6 | 3 | 47 | 1909 |
7 | 7 | 2 | 45 | 7409 |
8 | 7 | 3 | 46 | 11208 |
Whereas the VRP belongs to NP-Hard problems, if the problem size (the number of parameters, variables and constrains) increases, the computational time will increase exponentially. So, it is not possible to solve large-dimension problems by GAMS software and heuristic or Meta-heuristic methods should be applied to solve these problems.
5. Conclusion
In this paper, a bi-objective optimization model is presented for VRPTW with split delivery to transport non-adjacent products. Moreover, several real-world issues are considered, i.e. difficulty of route, rest time (depending on passed distance) and serve time (depending on type and amount of demand). Finally, the presented model is solved using AUGMECON method in several instances and the results are discussed.
References