American Institute of Mathematical Sciences

• Previous Article
An investigation of the most important factors for sustainable product development using evidential reasoning
• NACO Home
• This Issue
• Next Article
A new Monte Carlo based procedure for complete ranking efficient units in DEA models
December  2017, 7(4): 417-433. doi: 10.3934/naco.2017026

A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows

 1 Mazandaran University of Science and Technology, Department of Industrial Engineering, Babol, Iran 2 Department of Industrial Engineering, Yazd University, Yazd, Iran 3 Department of Industrial and System Engineering, Isfahan University of Technology, Isfahan, Iran 4 Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

Received  October 2016 Revised  August 2017 Published  October 2017

Fund Project: This paper was prepared at the occasion of The 12th International Conference on Industrial Engineering (ICIE 2016), Tehran, Iran, January 25-26,2016, with its Associate Editors of Numerical Algebra, Control and Optimization (NACO) being Assoc. Prof. A. (Nima) Mirzazadeh, Kharazmi University, Tehran, Iran, and Prof. Gerhard-Wilhelm Weber, Middle East Technical University, Ankara, Turkey.

Distribution of products within the supply chain with the highest quality is one of the most important competitive activities in industries with perishable products. Companies should pay much attention to the distribution during the design of their optimal supply chain. In this paper, a robust multi-trip vehicle routing problem with intermediate depots and time windows is formulated to deals with the uncertainty nature of demand parameter. A mixed integer linear programming model is presented to minimize total traveled distance, vehicles usage costs, earliness and tardiness penalty costs of services, and determine optimal routes for vehicles so that all customers' demands are covered. A number of random instances in different sizes (small, medium, and large) are generated and solved by CPLEX solver of GAMS to evaluate the robustness of the model and prove the model validation. Finally, a sensitivity analysis is applied to study the impact of the maximum available time for vehicles on the objective function value.

Citation: Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026
References:

show all references

References:
The scheme of the supply chain of the problem
CPU time comparison of the BBO and CPLEX
Sensitive analysis for $T_{max}$ parameter
Indices and sets
 $NC=\{1, 2, \dots, nc\}$ Set of customers $ND=\{1, 2, \dots, \ nk\}$ Set of intermediate depots $NT=\{1, 2, \dots, nt\}$ Set of customers and intermediate depots $NV=\{1, 2, \dots, nv\}$ Set of vehicles $NP=\{1, 2, \dots, np\}$ Set of trips $i, \ j, \ k, \ l$ Indices of network nodes $v$ Index of vehicles $p$ Index of trips $S$ An optional subset of customers $M$ A Large number
 $NC=\{1, 2, \dots, nc\}$ Set of customers $ND=\{1, 2, \dots, \ nk\}$ Set of intermediate depots $NT=\{1, 2, \dots, nt\}$ Set of customers and intermediate depots $NV=\{1, 2, \dots, nv\}$ Set of vehicles $NP=\{1, 2, \dots, np\}$ Set of trips $i, \ j, \ k, \ l$ Indices of network nodes $v$ Index of vehicles $p$ Index of trips $S$ An optional subset of customers $M$ A Large number
Parameters of problems
 $t_{ij}$ Traveling time from customer $i$ to customer $j$ ${QG}_k$ Quantity of product at intermediate depot $k$ ${VC}_{v\ }$ Capacity of vehicle $k$ ${DE}_j$ Forecasted demand of customer $j$ $\widetilde{{DE}_j}$ Non-deterministic demand of customer $j$ that belongs to the interval ${ [{DE}_j-\widehat{{DE}_j}, {DE}_j+\widehat{{DE}_j}]}$ $d_{ij}$ Distance between customer $i$ and customer $j$ ${DI}_V$ Maximum distance range of vehicle $v$ $Pe$ Penalty cost of earliness in servicing customers $Pl$ Penalty cost of tardiness in servicing customers ${CV}_v$ Usage cost of vehicle $v$ $e_{i}$ Lower bound of initial interval to service customer $i$ $l_{i}$ Upper bound of initial interval to service customer $i$ ${ee}_{i}$ Lower bound of secondary interval to service customer $i$ ${ll}_{i}$ Upper bound of secondary interval to service customer $i$ $T_{\max}$ Maximum time of vehicle usage $ul$ Unit loading time of vehicles in nodes with demand $uu$ Unit unloading time of vehicles in unloading platform
 $t_{ij}$ Traveling time from customer $i$ to customer $j$ ${QG}_k$ Quantity of product at intermediate depot $k$ ${VC}_{v\ }$ Capacity of vehicle $k$ ${DE}_j$ Forecasted demand of customer $j$ $\widetilde{{DE}_j}$ Non-deterministic demand of customer $j$ that belongs to the interval ${ [{DE}_j-\widehat{{DE}_j}, {DE}_j+\widehat{{DE}_j}]}$ $d_{ij}$ Distance between customer $i$ and customer $j$ ${DI}_V$ Maximum distance range of vehicle $v$ $Pe$ Penalty cost of earliness in servicing customers $Pl$ Penalty cost of tardiness in servicing customers ${CV}_v$ Usage cost of vehicle $v$ $e_{i}$ Lower bound of initial interval to service customer $i$ $l_{i}$ Upper bound of initial interval to service customer $i$ ${ee}_{i}$ Lower bound of secondary interval to service customer $i$ ${ll}_{i}$ Upper bound of secondary interval to service customer $i$ $T_{\max}$ Maximum time of vehicle usage $ul$ Unit loading time of vehicles in nodes with demand $uu$ Unit unloading time of vehicles in unloading platform
Non-decision variables
 ${{tt}_i}^p$ Presence time of vehicles at intermediate depot $i$ or customer node $i$ in trip $p$ ${tt}_{i}$ Presence time of vehicles at intermediate depot $i$ or customer $i$ ${{dd}_i}^p$ Distance traveled by vehicle in customer $i$ in trip $p$ ${{sd}_i}^p$ Distance traveled by vehicle in customer $i$ in trip $p$ or initial distance traveled by vehicle in trip $p$ and intermediate depot $i$ ${{ddd}_j}^v$ Distance traveled by each vehicle when arriving at intermediate depot $i$ ${LT}^p_v$ Total loading time of vehicle $v$ in trip $p$ ${UT}^p_v$ Total unloading time of vehicle $v$ in trip $p$ $\alpha$ Factor for converting total traveled distance to total transportation cost
 ${{tt}_i}^p$ Presence time of vehicles at intermediate depot $i$ or customer node $i$ in trip $p$ ${tt}_{i}$ Presence time of vehicles at intermediate depot $i$ or customer $i$ ${{dd}_i}^p$ Distance traveled by vehicle in customer $i$ in trip $p$ ${{sd}_i}^p$ Distance traveled by vehicle in customer $i$ in trip $p$ or initial distance traveled by vehicle in trip $p$ and intermediate depot $i$ ${{ddd}_j}^v$ Distance traveled by each vehicle when arriving at intermediate depot $i$ ${LT}^p_v$ Total loading time of vehicle $v$ in trip $p$ ${UT}^p_v$ Total unloading time of vehicle $v$ in trip $p$ $\alpha$ Factor for converting total traveled distance to total transportation cost
Decision variables
 $x_{ij}^{vp}$ Equals to 1, if vehicle $v$ traverses node $i$ to node $j$ in trip $p$; 0, otherwise. $y_{j vk}$ Equals to 1, if the demand of node $j$ is satisfied by intermediate depot $k$ and vehicle $v$; 0, otherwise. $F_{vk}$ Equals to 1, if vehicle $v$ is used in intermediate depot $k$; 0, otherwise. ${YE}_i$ Earliness in order to service customer $i$ ${YL}_i$ Tardiness in order to service customer $i$
 $x_{ij}^{vp}$ Equals to 1, if vehicle $v$ traverses node $i$ to node $j$ in trip $p$; 0, otherwise. $y_{j vk}$ Equals to 1, if the demand of node $j$ is satisfied by intermediate depot $k$ and vehicle $v$; 0, otherwise. $F_{vk}$ Equals to 1, if vehicle $v$ is used in intermediate depot $k$; 0, otherwise. ${YE}_i$ Earliness in order to service customer $i$ ${YL}_i$ Tardiness in order to service customer $i$
Solution details of the instance problem
 Vehicle 1 in intermediate depot 1 Intermediate depot 1 -customer 1 -customer 2 -Intermediate depot 2 -customer 3 -customer 4 -Intermediate depot 1 -customer 10 -customer 9 -customer 8 -Intermediate depot 1 Vehicle 2 in intermediate depot 2 Intermediate depot 2 -customer 5 -customer 6 -customer 7 -Intermediate depot 2
 Vehicle 1 in intermediate depot 1 Intermediate depot 1 -customer 1 -customer 2 -Intermediate depot 2 -customer 3 -customer 4 -Intermediate depot 1 -customer 10 -customer 9 -customer 8 -Intermediate depot 1 Vehicle 2 in intermediate depot 2 Intermediate depot 2 -customer 5 -customer 6 -customer 7 -Intermediate depot 2
Solution details of the instance problem
 Problem $n$ Depot Customers Types of Vehicles P1 5 3 2 2 P2 7 3 4 2 P3 9 4 5 3 P4 10 4 6 3 P5 13 5 8 4 P6 14 5 9 4 P7 15 5 10 5 P8 20 6 11 5 P9 30 8 22 7 P10 40 10 30 10
 Problem $n$ Depot Customers Types of Vehicles P1 5 3 2 2 P2 7 3 4 2 P3 9 4 5 3 P4 10 4 6 3 P5 13 5 8 4 P6 14 5 9 4 P7 15 5 10 5 P8 20 6 11 5 P9 30 8 22 7 P10 40 10 30 10
Calculation of robust parameters
 $\Gamma _{k}$ $\Gamma _{vp}$ $\rho$ $\left\lceil C^{\prime} /K^{\prime} \right\rceil$ $\left\lceil V^{\prime} /P^{\prime} \right\rceil$ (0.4, 0.8, 1)
 $\Gamma _{k}$ $\Gamma _{vp}$ $\rho$ $\left\lceil C^{\prime} /K^{\prime} \right\rceil$ $\left\lceil V^{\prime} /P^{\prime} \right\rceil$ (0.4, 0.8, 1)
Calculation of robust parameters
 Problem $\rho$ Objective value CPU Time (Sec) DP RP DP RP 1 0.4 6032.2 6853.859 0.2 2.25 $(\Gamma _{k} =1)$ 0.8 8118.738 $(\Gamma _{vp} =1)$ 1 8444.959 2 0.4 12046.2 13928.06 6.79 9.66 $(\Gamma _{k} =2)$ 0.8 17417.6 $(\Gamma _{vp} =1)$ 1 19273.68 3 0.4 24074.6 28076.63 198.73 308.06 $(\Gamma _{k} =2)$ 0.8 33606.15 $(\Gamma _{vp} =1)$ 1 36593.37 4 0.4 12055.3 13938.58 902.3 1102.64 $(\Gamma _{k} =2)$ 0.8 15974.48 $(\Gamma _{vp} =1)$ 1 17108.88 5 0.4 12071.4 13883.44 1449.01 1649.68 $(\Gamma _{k} =2)$ 0.8 16050.13 $(\Gamma _{vp} =2)$ 1 17182.43 6 0.4 12079.8 14016.31 1853.14 2309.01 $(\Gamma _{k} =2)$ 0.8 16143.44 $(\Gamma _{vp} =2)$ 1 17272.91 7 0.4 12761.1 15026.2 2520.08 2590.18 $(\Gamma _{k} =2)$ 0.8 18273.9 $(\Gamma _{vp} =2)$ 1 19473.44 8 0.4 17952.61 21548.52 3801.8 4106.63 $(\Gamma _{k} =2)$ 0.8 26857.1 $(\Gamma _{vp} =2)$ 1 27496.22 9 0.4 23721.4 29184.44 5682.12 6612.09 $(\Gamma _{k} =3)$ 0.8 35858.69 $(\Gamma _{vp} =3)$ 1 37241.65 10 0.4 30816.9 36681.36 10841.15 12394.88 $(\Gamma _{k} =4)$ 0.8 45953.11 $(\Gamma _{vp} =4)$ 1 51462.99
 Problem $\rho$ Objective value CPU Time (Sec) DP RP DP RP 1 0.4 6032.2 6853.859 0.2 2.25 $(\Gamma _{k} =1)$ 0.8 8118.738 $(\Gamma _{vp} =1)$ 1 8444.959 2 0.4 12046.2 13928.06 6.79 9.66 $(\Gamma _{k} =2)$ 0.8 17417.6 $(\Gamma _{vp} =1)$ 1 19273.68 3 0.4 24074.6 28076.63 198.73 308.06 $(\Gamma _{k} =2)$ 0.8 33606.15 $(\Gamma _{vp} =1)$ 1 36593.37 4 0.4 12055.3 13938.58 902.3 1102.64 $(\Gamma _{k} =2)$ 0.8 15974.48 $(\Gamma _{vp} =1)$ 1 17108.88 5 0.4 12071.4 13883.44 1449.01 1649.68 $(\Gamma _{k} =2)$ 0.8 16050.13 $(\Gamma _{vp} =2)$ 1 17182.43 6 0.4 12079.8 14016.31 1853.14 2309.01 $(\Gamma _{k} =2)$ 0.8 16143.44 $(\Gamma _{vp} =2)$ 1 17272.91 7 0.4 12761.1 15026.2 2520.08 2590.18 $(\Gamma _{k} =2)$ 0.8 18273.9 $(\Gamma _{vp} =2)$ 1 19473.44 8 0.4 17952.61 21548.52 3801.8 4106.63 $(\Gamma _{k} =2)$ 0.8 26857.1 $(\Gamma _{vp} =2)$ 1 27496.22 9 0.4 23721.4 29184.44 5682.12 6612.09 $(\Gamma _{k} =3)$ 0.8 35858.69 $(\Gamma _{vp} =3)$ 1 37241.65 10 0.4 30816.9 36681.36 10841.15 12394.88 $(\Gamma _{k} =4)$ 0.8 45953.11 $(\Gamma _{vp} =4)$ 1 51462.99
Sensitivity analysis of $T_{max}$ parameter
 P3 Objective value for different $T_{max}$ values 360 480 550 600 DP 24461.39 24074.6 23517.35 23517.35 RP ($\rho$=0.4) 28363.85 28076.63 28076.63 28076.63 RP ($\rho$=0.8) 34017.15 33606.15 33109.99 33109.99 RP ($\rho$=1) 37076.55 36593.37 33857.5 33857.5 AVE 30979.735 30587.6875 29640.3675 29640.3675
 P3 Objective value for different $T_{max}$ values 360 480 550 600 DP 24461.39 24074.6 23517.35 23517.35 RP ($\rho$=0.4) 28363.85 28076.63 28076.63 28076.63 RP ($\rho$=0.8) 34017.15 33606.15 33109.99 33109.99 RP ($\rho$=1) 37076.55 36593.37 33857.5 33857.5 AVE 30979.735 30587.6875 29640.3675 29640.3675
 [1] Lin Jiang, Song Wang. Robust multi-period and multi-objective portfolio selection. Journal of Industrial & Management Optimization, 2021, 17 (2) : 695-709. doi: 10.3934/jimo.2019130 [2] Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109 [3] Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113 [4] Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158 [5] Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325 [6] Musen Xue, Guowei Zhu. Partial myopia vs. forward-looking behaviors in a dynamic pricing and replenishment model for perishable items. Journal of Industrial & Management Optimization, 2021, 17 (2) : 633-648. doi: 10.3934/jimo.2019126 [7] Jian-Xin Guo, Xing-Long Qu. Robust control in green production management. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021011 [8] Tong Peng. Designing prorated lifetime warranty strategy for high-value and durable products under two-dimensional warranty. Journal of Industrial & Management Optimization, 2021, 17 (2) : 953-970. doi: 10.3934/jimo.2020006 [9] Bilel Elbetch, Tounsia Benzekri, Daniel Massart, Tewfik Sari. The multi-patch logistic equation. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021025 [10] Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076 [11] Bin Wang, Lin Mu. Viscosity robust weak Galerkin finite element methods for Stokes problems. Electronic Research Archive, 2021, 29 (1) : 1881-1895. doi: 10.3934/era.2020096 [12] Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100 [13] Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65 [14] Duy Phan, Lassi Paunonen. Finite-dimensional controllers for robust regulation of boundary control systems. Mathematical Control & Related Fields, 2021, 11 (1) : 95-117. doi: 10.3934/mcrf.2020029 [15] Paul A. Glendinning, David J. W. Simpson. A constructive approach to robust chaos using invariant manifolds and expanding cones. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020409 [16] Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067 [17] Bing Liu, Ming Zhou. Robust portfolio selection for individuals: Minimizing the probability of lifetime ruin. Journal of Industrial & Management Optimization, 2021, 17 (2) : 937-952. doi: 10.3934/jimo.2020005 [18] Liang Huang, Jiao Chen. The boundedness of multi-linear and multi-parameter pseudo-differential operators. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020291 [19] Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323 [20] Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364

Impact Factor: