ORIGINAL_ARTICLE
A Comparison of Extended Dijkstra and ACO Algorithm for Shortest Path Problem in Dynamic Networks with Delay Times
Shortest path problem is a typical routing optimization problem that is generally involved with a multi-criteria decision-making process. Therefore, the main objective of this paper is to find the shortest path in discrete-time dynamic networks based on bi-criteria of time and reliability by considering the effect of delay times that varies according to different departure time scenarios. Firstly, the well-known single-criterion Dijkstra’s algorithm is extended to fit the conditions of a bi-criteria problem. The solutions obtained from the extended Dijkstra was then compared with a proposed ant colony optimization (ACO) algorithm via a set of multi-objective performance metrics including CPU time, error ratio, spacing and diversity metrics. The analysis was made based on three network scales ranged from small (20-100 nodes), to medium (500-1900 nodes) and large (2000-10000 nodes). The computational results obtained from the analysis suggested that the extended Dijkstra’s algorithm has a higher efficiency in medium and large scaled networks. Furthermore, the comparison of the proposed ACO versus Dijkstra’s algorithm proved the preference of ACO for networks with larger-scaled (nodes over 5000), while, for smaller and medium-scaled networks (nodes 20-2000), the extended Dijkstra’s algorithm has a dominantly better performance in CPU time as compared to proposed ACO.
https://aie.ut.ac.ir/article_83031_5a12e13a014e2e0a2efd7782313fa977.pdf
2021-01-01
1
26
10.22059/jieng.2021.325262.1773
shortest path problem
Ant colony
Dijkstra
Delay time
dynamic network
Amir abbas
Shojaie
amir@ashojaie.com
1
School of Industrial Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran
LEAD_AUTHOR
Seyed Esmail
Seyedi Bariran
sm21356@utn.edu.my
2
School of Industrial Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran
AUTHOR
[1] Q. V. Martins, "On a multicriteria shortest path problem," European Journal of Operational Research, vol. 16, pp. 236-245, 1984.
1
[2] Skutella, "An introduction to network flows over time," in Research Trends in Combinatorial Optimization, ed: Springer, 2009, pp. 451-482.
2
[3] Ford and D. R. Fulkerson, Flows in networks vol. 1962: Princeton Princeton University Press, 1962.
3
[4] E. Aronson, "A survey of dynamic network flows," Annals of Operations Research, vol. 20, pp. 1-66, 1989.
4
[5] Kotnyek, "An annotated overview of dynamic network flows," 2003.
5
[6] A. Aloul, B. Al-Rawi, and M. Aboelaze, "Routing in Optical and Non-Optical Networks using Boolean Satisfiability," JCM, vol. 2, pp. 49-56, 2007.
6
[7] Dwivedi, R. Srivastava, P. Kalra, and Y. Singh, "Simplified neural network architecture for shortest path planning in optical network," in TENCON 2008-2008 IEEE Region 10 Conference, 2008, pp. 1-4.
7
[8] Erlebach and S. Stefanakos, "Wavelength conversion in shortest-path all-optical networks," Lecture notes in computer science, pp. 595-604, 2003.
8
[9] B. A. Teixeira, C. T. Batista, A. J. F. Cardoso, and J. d. S. Araújo, "A Genetic Algorithm Approach for Static Routing and Wavelength Assignment in All-Optical WDM Networks," in Portuguese Conference on Artificial Intelligence, 2017, pp. 421-432.
9
[10] Bhanja and D. Mishra, "Quality of service aware fuzzy dynamic routing and wavelength assignment technique in all optical networks," Photonic Network Communications, pp. 1-15, 2017.
10
[11] Gajendran, M. Pradeep, and S. B. Prabhu, "Systematic Analysis of Congestion Control in WDM Mesh Networks," Asian Journal of Applied Science and Technology (AJAST), vol. 1, p. 1, 2017.
11
[12] K. Pradhan, S. Keshri, K. Das, and T. De, "A heuristic approach based on dynamic multicast traffic grooming in WDM mesh networks," Journal of Optics, vol. 46, pp. 51-61, 2017.
12
[13] Ford Jr and D. R. Fulkerson, "Solving the transportation problem," Management Science, vol. 3, pp. 24-32, 1956.
13
[14] Bellman, "On a routing problem," DTIC Document1956.
14
[15] Brumbaugh-Smith and D. Shier, "An empirical investigation of some bicriterion shortest path algorithms," European Journal of Operational Research, vol. 43, pp. 216-224, 1989.
15
[16] J. Skriver and K. A. Andersen, "A label correcting approach for solving bicriterion shortest-path problems," Computers & Operations Research, vol. 27, pp. 507-524, 2000.
16
[17] Warburton, "Approximation of Pareto optima in multiple-objective, shortest-path problems," Operations research, vol. 35, pp. 70-79, 1987.
17
[18] Hassin, "Approximation schemes for the restricted shortest path problem," Mathematics of Operations research, vol. 17, pp. 36-42, 1992.
18
[19] H. Lorenz and D. Raz, "A simple efficient approximation scheme for the restricted shortest path problem," Operations Research Letters, vol. 28, pp. 213-219, 2001.
19
[20] Hao, D. Zhang, and X. Feng, "Model and algorithm for shortest path of multiple objectives," Journal of Southwest Jiaotong University, vol. 42, pp. 641-646, 2007.
20
[21] Y. Chen, W. H. Lam, A. Sumalee, Q. Li, and M. L. Tam, "Reliable shortest path problems in stochastic time-dependent networks," Journal of Intelligent Transportation Systems, vol. 18, pp. 177-189, 2014.
21
[22] Kwon, T. Lee, and P. Berglund, "Robust shortest path problems with two uncertain multiplicative cost coefficients," Naval Research Logistics (NRL), vol. 60, pp. 375-394, 2013.
22
[23] L. Chen and K. Tang, "Finding the Kth shortest path in a time‐schedule network," Naval Research Logistics (NRL), vol. 52, pp. 93-102, 2005.
23
[24] K. Cheung, "Iterative methods for dynamic stochastic shortest path problems," Naval Research Logistics (NRL), vol. 45, pp. 769-789, 1998.
24
[25] Murthy and S. S. Her, "Solving min‐max shortest‐path problems on a network," Naval Research Logistics (NRL), vol. 39, pp. 669-683, 1992.
25
[26] Tufekci, "Decomposition algorithms for finding the shortest path between a source node and a sink node of a network," Naval Research Logistics Quarterly, vol. 30, pp. 387-396, 1983.
26
[27] K. Ahuja, "Network flows," TECHNISCHE HOCHSCHULE DARMSTADT, 1993.
27
[28] Batta and S. S. Chiu, "Optimal obnoxious paths on a network: transportation of hazardous materials," Operations Research, vol. 36, pp. 84-92, 1988.
28
[29] R. Current, "Multiobjective design of transportation networks," 1981.
29
[30] Current and M. Marsh, "Multiobjective transportation network design and routing problems: Taxonomy and annotation," European Journal of Operational Research, vol. 65, pp. 4-19, 1993.
30
[31] Liu, H. Mu, H. Luo, and X. Li, "A simulated annealing for multi-criteria network path problems," Computers & Operations Research, vol. 39, pp. 3119-3135, 2012.
31
[32] Huang and S. Gao, "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, vol. 46, pp. 579-598, 2012.
32
[33] M. Nie and X. Wu, "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, vol. 43, pp. 597-613, 2009.
33
[34] C. Bezerra, E. F. Goldbarg, L. S. Buriol, and M. C. Goldbarg, "Grace: A generational randomized ACO for the multi-objective shortest path problem," in Evolutionary Multi-Criterion Optimization, 2011, pp. 535-549.
34
[35] Abbasi and S. Ebrahimnejad, "The cross-entropy method for solving bi-criteria network flow problems in discrete-time dynamic networks," Optimization Methods and Software, pp. 1-19, 2014.
35
[36] B. Reinhardt and D. Pisinger, "Multi-objective and multi-constrained non-additive shortest path problems," Computers & Operations Research, vol. 38, pp. 605-616, 2011.
36
[37] Nasrabadi and S. M. Hashemi, "Minimum cost time-varying network flow problems," Optimization Methods & Software, vol. 25, pp. 429-447, 2010.
37
[38] Maniezzo, M. Dorigo, V. Maniezzo, and A. Colorni, "Ant System: An Autocatalytic Optimizing Process," 1991.
38
[39] Dorigo and M. Birattari, "Ant colony optimization," in Encyclopedia of machine learning, ed: Springer, 2010, pp. 36-39.
39
[40] Dorigo, M. Birattari, and T. Stützle, "Ant colony optimization," Computational Intelligence Magazine, IEEE, vol. 1, pp. 28-39, 2006.
40
[41] Ekmen, Elçin Duygu. "A Study on Performance Evaluation of Optimization Algorithms in the Shortest Path Problem." PhD diss., Ankara Yıldırım Beyazıt Üniversitesi Fen Bilimleri Enstitüsü, 2020.
41
[42] Li, Xuan, Xiaofei Ye, and Lili Lu. "Dynamic Programming Approaches for Solving Shortest Path Problem in Transportation: Comparison and Application." In Green, Smart and Connected Transportation Systems, pp. 141-160. Springer, Singapore, 2020.
42
[43] Kumawat, Sunita, Chanchal Dudeja, and Pawan Kumar. "An Extensive Review of Shortest Path Problem Solving Algorithms." In 2021 5th International Conference on Intelligent Computing and Control Systems (ICICCS), pp. 176-184. IEEE, 2021.
43
[44] Hughes, Michael S., Brian J. Lunday, Jeffrey D. Weir, and Kenneth M. Hopkinson. "The multiple shortest path problem with path de-confliction." European Journal of Operational Research 292, pp.818-829, no. 3 (2021).
44
ORIGINAL_ARTICLE
Proposing a New Method for Transportation Planning Considering Traffic Congestion
Traffic congestion is one of the issues in transportation planning which imposes environmental consequences and costs. Therefore, decision-makers and policymakers should focus on appropriate transportation planning models. One of the approaches to relieve traffic congestion is imposing tolls on the users. In the present paper, attempts are made to present three transportation planning and traffic congestion management models. The first model assumes that the transportation network and the traffic flows within it are determined. Decision-maker seeks to adjust the transportation network flows so that traffic congestion can be prevented. In the second model, unlike the first one, attempts are made to design urban transportation networks via the development of routes. The third model is a mixture of the first and second models. All models proposed here are bi-objective which were addressed under uncertain conditions and disturbances. According to the results, a decision-making model was extended to rank routes. In the end, a numerical example is considered for analyzing and evaluating the proposed models. The results of the numerical example showed that the first model is the most inefficient and the third model is the most efficient. Since the proposed model can be implemented in road networks in addition to urban transportation networks, the application of the proposed models is demonstrated based on a real-world case study. The case study results showed that the efficiency of road network depends on the time interval.
https://aie.ut.ac.ir/article_83033_e23ca67abc6229ffbab10a722edf6dfd.pdf
2021-01-01
27
46
10.22059/jieng.2021.325270.1774
Flow Optimization
Efficiency
Environmental Criterion
Uncertainty
Toll
Ardavan
Babaei
ardvan.babaei@ie.sharif.edu
1
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran
AUTHOR
Majid
Khedmati
khedmati@sharif.edu
2
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran
AUTHOR
Mohammad Reza
Akbari Jokar
reza.akbari@sharif.edu
3
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.
LEAD_AUTHOR
[1] Figueiras, P., Gonçalves, D., Costa, R., Guerreiro, G., Georgakis, P., and Jardim-Gonçalves, R. (2019). Novel Big Data-supported dynamic toll charging system: Impact assessment on Portugal’s shadow-toll highways. Computers and Industrial Engineering, 135(June), 476–491.
1
[2] Assadipour, G., Ke, G. Y., and Verma, M. (2016). A toll-based bi-level programming approach to managing hazardous materials shipments over an intermodal transportation network. Transportation Research Part D, 47, 208–221.
2
[3] He, (2016). Optimal Time-Varying Pricing for Toll Roads Under Multiple Objectives : A Simulation-Based Optimization Approach.
3
[4] Tsai, J.-F., and Li, S.-C. (2019). Cordon tolling for mixed traffic flow. Transportmetrica A: Transport Science, 15(2), 1662–1687.
4
[5] Harks, T., Schröder, M., and Vermeulen, D. (2019). Toll caps in privatized road networks. European Journal of Operational Research, 276(3), 947–956.
5
[6] Chen, J., Zhao, F., Liu, Z., Ou, X., and Hao, H. (2017). Greenhouse gas emissions from road construction in China: A province-level analysis. Journal of Cleaner Production, 168, 1039–1047.
6
[7] Xu, C., Zhao, J., and Liu, P. (2019). A Geographically Weighted Regression Approach to Investigate the Effects of Traffic Conditions and Road Characteristics on Air Pollutant Emissions. Journal of Cleaner Production. https://doi.org/10.1016/j.jclepro.2019.118084
7
[8] Rodriguez Roman, D., and Ritchie, S. G. (2017). Accounting for population exposure to vehicle-generated pollutants and environmental equity in the toll design problem. International Journal of Sustainable Transportation, 11(6), 406–421.
8
[9] Sobrino, N., Monzon, A., and Hernandez, S. (2016). Reduced Carbon and Energy Footprint in Highway Operations: The Highway Energy Assessment (HERA) Methodology. Networks and Spatial Economics, 16(1), 395–414.
9
[10] Wang, Z., Deng, X., Wong, C., Li, Z., and Chen, J. (2018). Learning urban resilience from a social-economic-ecological system perspective: A case study of Beijing from 1978 to 2015. Journal of Cleaner Production, 183, 343–357.
10
[11] Patil, G. R. (2016). Emission-based static traffic assignment models. Environmental Modeling and Assessment, 21(5), 629–642.
11
[12] Lv, Y., Wang, S., Gao, Z., Li, X., and Sun, W. (2018). Design of a heuristic environment-friendly road pricing scheme for traffic emission control under uncertainty. (June). https://doi.org/10.1016/j.jenvman.2018.11.042
12
[13] Edrisi, A., and Askari, M. (2019). Probabilistic budget allocation for improving efficiency of transportation networks in pre-and post-disaster phases. International Journal of Disaster Risk Reduction, 101113. https://doi.org/10.1016/j.ijdrr.2019.101113
13
[14] Sathiaraj, D., Punkasem, T. on, Wang, F., and Seedah, D. P. K. (2018). Data-driven analysis on the effects of extreme weather elements on traffic volume in Atlanta, GA, USA. Computers, Environment and Urban Systems, 72(February), 212–220.
14
[15] Li, , Kappas, M., and Li, Y. (2018). Exploring the coastal urban resilience and transformation of coupled human-environment systems. Journal of Cleaner Production, 195, 1505–1511.
15
[16] Wang, J., Hu, X., and Li, C. (2018). Optimization of the freeway truck toll by weight policy, including external environmental costs. Journal of Cleaner Production. https://doi.org/10.1016/j.jclepro.2018.02.228
16
[17] Elluru, S., Gupta, H., Kaur, H., and Singh, S. P. (2017). Proactive and reactive models for disaster resilient supply chain. Annals of Operations Research, 1–26. https://doi.org/10.1007/s10479-017-2681-2
17
[18] Shirazi, M., Aashtiani, H. Z., and Quadrifoglio, L. (2017). Estimating the minimal revenue tolls in large-scale roadway networks using the dynamic penalty function method. Computers and Industrial Engineering, 107, 120–127.
18
[19] Shirazi, M., and Aashtiani, H. Z. (2015). Solving the minimum toll revenue problem in real transportation networks. Optimization Letters, 9(6), 1187–1197.
19
[20] Stefanello, F., Buriol, L. S., Hirsch, M. J., Pardalos, P. M., Querido, T., Resende, M. G. C., and Ritt, M. (2017). On the minimization of traffic congestion in road networks with tolls. Annals of Operations Research, 249(1–2), 119–139.
20
[21] Xu, M., Wang, G., Grant-Muller, S., and Gao, Z. (2017). Joint road toll pricing and capacity development in discrete transport network design problem. Transportation, 44(4), 731–752.
21
[22] Cheng, Q., Liu, Z., and Szeto, W. Y. (2019). A cell-based dynamic congestion pricing scheme considering travel distance and time delay. Transportmetrica B: Transport Dynamics, 7(1), 1286–1304.
22
[23] Liu, Z., and Song, Z. (2019). Strategic planning of dedicated autonomous vehicle lanes and autonomous vehicle/toll lanes in transportation networks. Transportation Research, Part C: Emerging Technologies, 106(July), 381–403.
23
[24] Odeck, J., and Welde, M. (2017). The accuracy of toll road traffic forecasts: An econometric evaluation. Transportation Research Part A: Policy and Practice, 101, 73–85.
24
[25] Laurent, A. B., Vallerand, S., van der Meer, Y., and D’Amours, S. (2019). CarbonRoadMap: A multicriteria decision tool for multimodal transportation. International Journal of Sustainable Transportation, 8318. https://doi.org/10.1080/15568318.2018.1540734
25
[26] Alasad, R., and Motawa, I. (2015). Dynamic demand risk assessment for toll road projects. Construction Management and Economics, 33(10), 799–817.
26
[27] Wang, D. (2019). Performance assessment of major global cities by DEA and Malmquist index analysis. Computers, Environment and Urban Systems, 77(July), 101365. https://doi.org/10.1016/j.compenvurbsys.2019.101365
27
[28] Figueiras, P., Gonçalves, D., Costa, R., Guerreiro, G., Georgakis, P., and Jardim-Gonçalves, R. (2019). Novel Big Data-supported dynamic toll charging system: Impact assessment on Portugal’s shadow-toll highways. Computers and Industrial Engineering, 135(June), 476–491.
28
[29] Klimberg, R. K., and Ratick, S. J. (2008). Modeling data envelopment analysis (DEA) efficient location/allocation decisions. Computers and Operations Research, 35(2), 457–474.
29
[30] Cheng, Y., and Gao, H. L. (2015). Matrix-Type Network DEA Model with Its Application Based on Input-Output Tables. Mathematical Problems in Engineering, 2015. https://doi.org/10.1155/2015/505941
30
[31] Wang, Y., and Zeng, Z. (2018). Data-Driven solutions to transportation problems. Elsevier.
31
[32] Ghasemi, M.-R., Ignatius, J., Emrouznejad, A. (2014). A bi-objective weighted model for improving the discrimination power in MCDEA. European Journal of Operational Research, 233, 640–650.
32
[33] Bootaki, B., Mahdavi, I., and Paydar, M. M. (2015). New bi-objective robust design-based utilisation towards dynamic cell formation problem with fuzzy random demands. International Journal of Computer Integrated Manufacturing, 28(6), 577–592.
33
[34] Tang, L., Jiang, W., and Saharidis, G. K. D. (2013). An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions. Annals of Operations Research, 210(1), 165–190.
34
[35] Osman, H., and Demirli, K. (2010). A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection. International Journal of Production Economics, 124(1), 97–105.
35
[36] Hadi-Vencheh, A., Hatami-Marbini, A., Ghelej Beigi, Z., and Gholami, K. (2015). An inverse optimization model for imprecise data envelopment analysis. Optimization, 64(11), 2441–2454.
36
ORIGINAL_ARTICLE
An L-Shaped Method to Solve a Stochastic Blood Supply Chain Network Design Problem in a Natural Disaster
Level of blood and blood products in human body is very important. Therefor, managing supply of blood is critical issue in healthcare system specially when the system faced with high demand for the product. In natural disasters, demand for blood units increase sharply because of injuries. Hence, efficiency in blood supply chain management play a significant role in this situation in supplying blood for transfusion centers, it is vital to supply in right time to prevent from casualties. Present paper proposes an optimization model for designing blood supply chain network in case of an earthquake disaster. The proposed two-stage stochastic model is Programmed based on scenarios for earthquake in a populated mega-city. The designed network has three layers; first layer is donation areas, the second layer consists distribution centers and facilities and the last layer is transfusion centers. In proposed two-stage stochastic optimization model, decisions of locating permanent collection facilities and amount of each blood type pre-inventory are made in first stage and operation decisions that have dependent on possible scenarios are made in second stage. The model also considers the possibility of blood transfusion between different blood types and its convertibility to blood derivatives regarding medical requirements. In order to solve the proposed two-stage stochastic model, L-shaped algorithm, an efficient algorithm to solve scenario based stochastic models, has been used. In addition, application of the model and the algorithm tests with real data of likely earthquake in Tehran mega city (Densest city of Iran).
https://aie.ut.ac.ir/article_83035_4733a1100cfe8ca1ee6993b8af592100.pdf
2021-01-01
47
68
10.22059/jieng.2021.325375.1776
Blood Supply Chain
Network Design
Stochastic Programming
L-Shaped Exact Method
Faraz
Salehi
salehi.faraz.90@gmail.com
1
Department of Industrial Engineering and Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran.
LEAD_AUTHOR
Yasin
Allahyari Emamzadeh
allahyari.yasin@gmail.com
2
Department of Industrial Engineering and Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran.
AUTHOR
Seyyed Mohammad Javad
Mirzapour Al-E-Hashem
b.mirzapour@gmail.com
3
Department of Industrial Engineering and Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran.
AUTHOR
Reyhaneh
Shafiei Aghdam
reyhaneh_ashofteh@yahoo.com
4
Department of Industrial Engineering and Management Systems, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran.
AUTHOR
[1] Masoud Esmaeilikia, B. F. (2016). Tactical supply chain planning models with inherent flexibility: definition and review. Annals of Operations Research, 407-427.
1
[2] T. Melo, S. N.-d.-G. (2009). Facility location and supply chain management - A review. European Journal of Operational Research, vol. 196, issue 2, 401-412.
2
[3] Barbarosoǧlu G, A. Y. (2004). A two-stage stochastic programming framework for transportation planning in disaster response. The Journal of the Operational Research Society, vol. 55(1), pages 43-53.
3
[4] Abolghasemi, H. R.-D. (2008). Revisiting blood transfusion preparedness: experience from the Bam earthquake response. Prehospital Disaster Med. 23 (5), 391–394.
4
[5] Hess, J. T. (2003). Blood use in war and disaster: lessons from the past century. Transfusion 43 (11), 1622–1633.
5
[6] Retrieved from www.redcross.com.
6
[7] Williamson L. M., D. D. (2013). Challenges in the management of the blood supply. Lancet, V(381), I 9880, Pages 1866-1875.
7
[8] Rabinowits, M. (1973). Blood bank Inventory Policies: a computer simulation. Health Service Research, Vol. 8, No. 4, pp. 271-282, 1973.
8
[9] Khalilpourazari , S., Soltanzadeh, S., & Weber, G. (2019). Designing an efficient blood supply chain network in crisis:neural learning, optimization and case study. Annals of Operations Research 289, 123–152.
9
[10] Khalilpourazari, S., and Arshadi Khamseh, A. (2017). Bi-objective emergency blood supply chain network design in earthquake considering earthquake magnitude: a comprehensive study with real world application. Annals of Operations Research V(283), 355–393.
10
[11] Sahin G., M. S. (2007). Locational analysis for regionalization of Turkish red Crescent blood ser Computers and Operations Research, Vol. 34, No. 3, pp. 692-704.
11
[12] Cetin E., S. L. (2009). A Blood Bank Location Model: A Multi-objective Approach. European Journal of Pure and Applied Mathematics, Vol. 2, No. 1, pp. 112-124.
12
[13] Gunpinar, (2013). Supply Chain Optimization of Blood Products. Ph.D. Dissertation, University of South Florida.
13
[14] Farrokhizadeh, E., Seyfi‑Shishavan, S. A., and Satoglu, S. I. (2021). Blood supply planning during natural disasters under uncertainty: a novel bi‑objective model and an application for red crescent. Annals of Operations Research.
14
[15] Jabbarzadeh, A. F. (2014). Dynamic supply chain network design for the supply of blood in disasters: A robust model with real world application. Transportation Research , Part E: Logistics and Transportation Review 70, 225-244.
15
[16] Nagurney A., M. A. (2012). Supply chain network design of a sustainable blood banking system. In T. J. Boone, Sustainable Supply Chains: Models. Methods and Public Policy Implications (pp. pp. 49–72.). London, England: Springer.
16
[17] Sha Y., H. J. (2012). The multi-period location-allocation problem of engineering emergency blood supply systems. Systems Engineering Procedia, 21-28.
17
[18] Fazli-Khalaf, M., Khalilpourazari, S., and Mohammadi, M. (2017). Mixed robust possibilistic flexible chance constraint optimization model for emergency blood supply chain network. Annals of Operations Research volume 283, 1079–1109.
18
[19] Ghasemi, P., Khalili-Damghani, K., Hafezalkotob, A., and Raissi, S. (2019). Uncertain multi-objective multi-commodity multi-period multi-vehicle location-allocation model for earthquake evacuation planning. Applied Mathematics and Computation 350, Pages 105-132.
19
[20] Asadpour, M., Boyer, O., and Tavakkoli-Moghaddam, R. (2020). A Blood Supply Chain Network with Backup Facilities Considering Blood Groups and Expiration Date: A Real-world Application. International Journal of Engineering, Volume:34 Issue: 2, 470 - 479.
20
[21] Karadağ, İ., Keskin, M., and Yiğit , V. (2021). Re-design of a blood supply chain organization with mobile units. Methodologies and Application.
21
[22] GhatrehSaman, M., Hosseini Motlagh, S., and Homaei, S. (2020). A reactive phase against disruptions for designing a proactive platelet supply network. Transportation Research.
22
[23] Kamyabniya, A., Noormohammadzadeh, Z., Sauré, A., and Patrick, J. (2021). A robust integrated logistics model for age-based multi-group platelets in disaster relief operations. Transportation Research.
23
[24] Soltani, M., Aziz Mohammadi, R., Hosseini, S., and Zanjani, M. (2021). A New Model for Blood Supply Chain Network Design In Disasters Based on Hub Location Approach Considering Intercity Transportation. International Journal of Industrial Engineering and Production Research.
24
[25] Hamdan, B., and Diabat, A. (2020). Robust design of blood supply chains under risk of disruptions using Lagrangian relaxation. Transportation Research.
25
[26] Birge J. R., L. F. (2011). Introduction to stochastic programming. Springer Science and Business Media.
26
[27] Salehi, F., Mahootchi, M., and Moattar Husseini, S. (2017). Developing a robust stochastic model for designing a blood supply chain network in a crisis: a possible earthquake in Tehran. Annals of Operations Research.
27
[28] Dehghani, H. (2020). Probabilistic prediction of earthquake by bivariate distribution. Asian Journal of Civil Engineering.
28
[29] Mete HO, Z. Z. (2010). Stochastic optimization of medical supply location and distribution in disaster management. International Journal of Production Economics 126(1, 76-84.
29
[30] Tabatabaie M., A. A. (2010). Estimating blood transfusion requirements in preparation for a major earthquake: the Tehran, Iran study. Prehospital and disaster medicine, 25(03), 246-252.
30
ORIGINAL_ARTICLE
Reliable Urban Transportation Network Design Problem Considering Recurrent Traffic Congestions
Traffic congestion is one of the main reasons for the unsustainability of an urban transportation network. Changes in travel demand and streets’ capacity lead to traffic congestion in urban transportation networks, which is known as recurrent traffic congestion. This study aims to assess the performance reliability of urban transportation networks subject to recurrent traffic congestion conditions in order to help travelers to find alternative non-congested routes. A non-congested route is a route without any congested link. The network reliability is defined and modeled as two different scenarios; users’ unawareness of the network’s traffic congestion and users’ ongoing awareness of the network’s traffic congestion. In addition, a reliable network design model is provided to optimize the reliability of the network taking into account street widening policy and budget constraints. Lastly, a Quantum-Inspired Evolutionary Meta-Heuristic Algorithm is adopted; while maintaining accuracy, to reduce problem-solving time and providing the possibility of solving large-scale problems for real networks. To show the applicability of the proposed models and algorithm, they have been implemented on the Sioux Falls transportation network. The results indicate users’ awareness of traffic congestion in the network increases its reliability, and centrally located links are the first candidates for street widening.
https://aie.ut.ac.ir/article_83036_12e8968d2f3b8f6bc9eb3dc45b3212a5.pdf
2021-01-01
69
89
10.22059/jieng.2021.326142.1784
reliability
Recurrent Traffic Congestion
Traffic Awareness
Sustainable Urban Transportation Network
Network Design
Ali
Riahi Samani
rhsamani@memphis.edu
1
Department of Civil Engineering University of Memphis Memphis, Tennessee, USA
AUTHOR
Seyyed-Nader
Shetab-Boushehri
shetab@cc.iut.ac.ir
2
Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran.
AUTHOR
Reza
Mahmoudi
reza.mahmoudi@ucalgary.ca
3
Department of Civil Engineering, University of Calgary, Calgary, Alberta, Canada.
LEAD_AUTHOR
[1] Khayamim, R., et al., A sustainable approach for selecting and timing the urban transportation infrastructure projects in large-scale networks: A case study of Isfahan, Iran. Sustainable Cities and Society, 2020. 53: p. 101981.
1
[2] Mahmoudi, R., et al., Determining the relative importance of sustainability evaluation criteria of urban transportation network. Sustainable Cities and Society, 2019. 47: p. 101493.
2
[3] Mahmoudi, R.S., Nader; Hejazi, Reza; Emrouznejad, Ali; Rajabi, Parisa;, A hybrid egalitarian bargaining game-DEA and sustainable network design approach for evaluating, selecting and scheduling urban road construction projects. Transportation Research Part E: Logistics and Transportation Review, 2019. 130: p. 161-183.
3
[4] Hojjati-Emami, K., B. Dhillon, and K. Jenab, Reliability prediction for the vehicles equipped with advanced driver assistance systems (ADAS) and passive safety systems (PSS). International Journal of Industrial Engineering Computations, 2012. 3(5): p. 731-742.
4
[5] Du, Z.-P. and A. Nicholson, Degradable transportation systems: sensitivity and reliability analysis. Transportation Research Part B: Methodological, 1997. 31(3): p. 225-237.
5
[6] Naresky, J.J., Reliability definitions. IEEE Transactions on Reliability, 1970. 19(4): p. 198-200.
6
[7] Sumalee, A., D.P. Watling, and S. Nakayama, Reliable network design problem: case with uncertain demand and total travel time reliability. Transportation Research Record, 2006. 1964(1): p. 81-90.
7
[8] Chen, A., et al., Transport network design problem under uncertainty: a review and new developments. Transport Reviews, 2011. 31(6): p. 743-768.
8
[9] Wardrop, J.G. and J. Whitehead, some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, 1952. 1(5): p. 767-768.
9
[10] Herman, R. and T. Lam, Trip time characteristics of journeys to and from work. Transportation and traffic theory, 1974. 6: p. 57-86.
10
[11] Richardson, A. and M. Taylor, Travel time variability on commuter journeys. High Speed Ground Transportation Journal, 1978. 12(1).
11
[12] Polus, A., A study of travel time and reliability on arterial routes. Transportation, 1979. 8(2): p. 141-151.
12
[13] Al-Deek, H. and E.B. Emam, New methodology for estimating reliability in transportation networks with degraded link capacities. Journal of intelligent transportation systems, 2006. 10(3): p. 117-129.
13
[14] Van Lint, J., H.J. Van Zuylen, and H. Tu, Travel time unreliability on freeways: Why measures based on variance tell only half the story. Transportation Research Part A: Policy and Practice, 2008. 42(1): p. 258-277.
14
[15] Pu, W., Analytic relationships between travel time reliability measures. Transportation Research Record: Journal of the Transportation Research Board, 2011(2254): p. 122-130.
15
[16] Institute, T.T., Providing a Highway System with Reliable Travel Times. F-SHRP Web Document 3. Transportation Research Board of the National Academies, Washington, D. C., 2003.
16
[17] Clark, S. and D. Watling, Modelling network travel time reliability under stochastic demand. Transportation Research Part B: Methodological, 2005. 39(2): p. 119-140.
17
[18] Dui, H., et al., Model and simulation analysis for the reliability of the transportation network. Journal of Simulation, 2020: p. 1-10.
18
[19] Liu, J., et al., Connectivity Reliability on an Urban Rail Transit Network from the Perspective of Passenger Travel. Urban Rail Transit, 2020. 6(1): p. 1-14.
19
[20] Wakabayashi, H. and Y. Iida, Improvement of road network reliability with traffic management. IFAC Proceedings Volumes, 1994. 27(12): p. 603-608.
20
[21] Lee, S., B. Moon, and Y. Asakura, Reliability analysis and calculation on large scale transport networks. Reliability of transport networks. Research Studies Press Ltd, 2000.
21
[22] Chen, A., P. Kasikitwiwat, and C. Yang, Alternate capacity reliability measures for transportation networks. Journal of Advanced Transportation, 2013. 47(1): p. 79-104.
22
[23] Chiou, J.-M., H.-T. Liou, and W.-H. Chen, Modeling Time-Varying Variability and Reliability of Freeway Travel Time Using Functional Principal Component Analysis. IEEE Transactions on Intelligent Transportation Systems, 2019.
23
[24] Zhang, Z., et al., Analyzing travel time reliability and its influential factors of emergency vehicles with generalized extreme value theory. Journal of Intelligent Transportation Systems, 2019. 23(1): p. 1-11.
24
[25] Lu, C., et al., Incorporating the standstill distance and time headway distributions into freeway car-following models and an application to estimating freeway travel time reliability. Journal of Intelligent Transportation Systems, 2019: p. 1-20.
25
[26] Knoop, V.L., et al., Link-level vulnerability indicators for real-world networks. Transportation Research Part A: Policy and Practice, 2012. 46(5): p. 843-854.
26
[27] El-Rashidy, R.A. and S.M. Grant-Muller, An assessment method for highway network vulnerability. Journal of Transport Geography, 2014. 34: p. 34-43.
27
[28] Wang, D.Z., et al., Identification of critical combination of vulnerable links in transportation networks–a global optimisation approach. Transportmetrica A: Transport Science, 2016. 12(4): p. 346-365.
28
[29] Bagloee, S.A., et al., Identifying critical disruption scenarios and a global robustness index tailored to real life road networks. Transportation Research Part E: Logistics and Transportation Review, 2017. 98: p. 60-81.
29
[30] Vodák, R., et al., A deterministic approach for rapid identification of the critical links in networks. PloS one, 2019. 14(7).
30
[31] Gecchele, G., R. Ceccato, and M. Gastaldi, Road Network Vulnerability Analysis: Case Study Considering Travel Demand and Accessibility Changes. Journal of Transportation Engineering, Part A: Systems, 2019. 145(7): p. 05019004.
31
[32] Cantillo, V., L.F. Macea, and M. Jaller, Assessing vulnerability of transportation networks for disaster response operations. Networks and Spatial Economics, 2019. 19(1): p. 243-273.
32
[33] Tian, Z., et al., Key links identification for urban road traffic network based on temporal-spatial distribution of traffic congestion. Modern Physics Letters B, 2019. 33(25): p. 1950307.
33
[34] Guo, S., et al., Identifying the most influential roads based on traffic correlation networks. EPJ Data Science, 2019. 8(1): p. 1-17.
34
[35] Poorzahedy, H. and S.N.S. Bushehri, Network performance improvement under stochastic events with long-term effects. Transportation, 2005. 32(1): p. 65-85.
35
[36] Chen, H. and H.A. Rakha, Real-time travel time prediction using particle filtering with a non-explicit state-transition model. Transportation Research Part C: Emerging Technologies, 2014. 43: p. 112-126.
36
[37] Iida, Y. and H. Wakabayashi. An approximation method of terminal reliability of road network using partial minimal path and cut sets. in Transport policy, management & technology towards 2001: selected proceedings of the fifth world conference on transport research. 1989.
37
[38] Valiant, L.G., The complexity of enumeration and reliability problems. SIAM Journal on Computing, 1979. 8(3): p. 410-421.
38
[39] Shier, D.R., Network reliability and algebraic structures. 1991: Clarendon Press.
39
[40] Konak, A. and A. Smith. A general upperbound for all-terminal network reliability and its uses. in Proceedings of the Industrial Engineering Research Conference. 1998.
40
[41] Sharafat, A.R. and O.R. Ma'rouzi, All-terminal network reliability using recursive truncation algorithm. IEEE Transactions on Reliability, 2009. 58(2): p. 338-347.
41
[42] Satyanarayana, A., A unified formula for analysis of some network reliability problems. IEEE Transactions on Reliability, 1982. 31(1): p. 23-32.
42
[43] Fishman, G.S., A Monte Carlo sampling plan for estimating network reliability. Operations Research, 1986. 34(4): p. 581-594.
43
[44] Karp, R.M. and M. Luby. Monte-Carlo algorithms for enumeration and reliability problems. in Foundations of Computer Science, 1983., 24th Annual Symposium on. 1983. IEEE.
44
[45] Everitt, B. and A. Skrondal, The Cambridge dictionary of statistics. Vol. 106. 2002: Cambridge University Press Cambridge.
45
[46] Farahani, R.Z., et al., A review of urban transportation network design problems. European Journal of Operational Research, 2013. 229(2): p. 281-302.
46
[47] Bryden, K.M., et al., Optimization of heat transfer utilizing graph based evolutionary algorithms. International Journal of Heat and Fluid Flow, 2003. 24(2): p. 267-277.
47
[48] Beheshti, A. and S. Hejazi, A Quantum evolutionary algorithm for the vehicle routing problem with delivery time cost. International Journal of Industrial Engineering and Production Research, 2014. 25(4): p. 287-295.
48
[49] Mani, N. and A. Mani, Solving Combinatorial Optimization problems with Quantum inspired Evolutionary Algorithm Tuned using a Novel Heuristic Method. arXiv preprint arXiv:1612.08109, 2016.
49
[50] Narayanan, A. and M. Moore. Quantum-inspired genetic algorithms. in Evolutionary Computation, 1996., Proceedings of IEEE International Conference on. 1996. IEEE.
50
[51] Han, K.-H. and J.-H. Kim. Genetic quantum algorithm and its application to combinatorial optimization problem. in Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. 2000. IEEE.
51
[52] Han, K.-H. and J.-H. Kim, Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE transactions on evolutionary computation, 2002. 6(6): p. 580-593.
52
[53] Zhang, G., Quantum-inspired evolutionary algorithms: a survey and empirical study. Journal of Heuristics, 2011. 17(3): p. 303-351.
53
[54] Kourank Beheshti, A. and S.R. Hejazi, A Quantum Evolutionary Algorithm for the Vehicle Routing Problem with Single-sided Time Window Setting. International Journal of Industrial Engineering & Production Research, 2014. 25(4): p. 287-295.
54
ORIGINAL_ARTICLE
Unrelated Parallel Machines Scheduling with Sequence-Dependent Setup Times to Minimize Makespan and Tariff Charged Energy Consumption
An appropriate trade-off between total electricity costs and makespan can lead to good production planning and reduce unnecessary energy consumption. Time-of-use (TOU) electricity pricing policy has been executed in many countries which enabled industrial consumers with high energy consumption to reduce their energy costs. In this study, an unrelated parallel machines scheduling problem is considered for minimizing makespan and also energy consumption costs. Due to the importance of sequence-dependent setup times in production environments, they are considered according to the restricted duration of time periods under TOU policy. These considerations are added to the current literature. A mixed-integer bi-objective mathematical model is presented and the ε-constraint method is applied to solve small and also medium-sized instances. Because the problem is shown to be NP-hard, several large-sized instances are approximately solved using Multiple Objective Particle Swarm Optimization algorithm, and Multiple Objective Simulated Annealing algorithm. Computational experiments are conducted on randomly generated data. The results show the efficiency and appropriate performance of the proposed methods.
https://aie.ut.ac.ir/article_83037_ed730a0218a4bf804188afa36b61cc5b.pdf
2021-01-01
91
113
10.22059/jieng.2021.326682.1788
Unrelated parallel machines scheduling
Makespan
Energy consumption
Time-of-use electricity price
Sequence-dependent setup times
Taha
Keshavarz
taha_keshavarz@semnan.ac.ir
1
Department of Industrial Engineering, Semnan University, Semnan, Iran
LEAD_AUTHOR
Erfaneh
Karimi
erfanehkarimi@stu.yazd.ac.ir
2
Department of Industrial Engineering, Yazd University, Yazd, Iran
AUTHOR
Majid
Shakhsi-Niaei
m.niaei@yazd.ac.ir
3
Department of Industrial Engineering, Yazd University, Yazd, Iran
AUTHOR
[1] EI Energy use in industry, https://www.eia.gov/energyexplained/use-of-energy/industry.php ; 2020 [Accessed 28 July 2020].
1
[2] Li, L., Li, C., Tang, Y., & Li, L. An integrated approach of process planning and cutting parameter optimization for energy-aware CNC machining. Journal of Cleaner Production. 2017;162: 458-73.
2
[3] Zeng, Y., Che, A., & Wu, X. Bi-objective scheduling on uniform parallel machines considering electricity cost. Engineering Optimization. 2018;50(1): 19-36.
3
[4] Wu, X., & Che, A. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega. 2019; 82: 155-65.
4
[5] Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., & Sassani, F. Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research. 2009; 36(12): 3224-30.
5
[6] Angel, E., Bampis, E., & Kacem, F. Energy aware scheduling for unrelated parallel machines. IEEE International Conference on Green Computing and Communications: IEEE;2012 .p. 533-40.
6
[7] Liang, P., Yang, H. D., Liu, G. S., & Guo, J. H. An ant optimization model for unrelated parallel machine scheduling with energy consumption and total tardiness. Mathematical Problems in Engineering. 2015. doi: 1155/2015/907034
7
[8] Li, Z., Yang, H., Zhang, S., & Liu, G. Unrelated parallel machine scheduling problem with energy and tardiness cost. The International Journal of Advanced Manufacturing Technology. 2016; 84(1-4): 213-26.
8
[9] Cota, L. , Coelho, V. N., Guimarães, F. G., & Souza, M. J. Bi‐criteria formulation for green scheduling with unrelated parallel machines with sequence‐dependent setup times. International Transactions in Operational Research. 2018 doi: 10.1111/itor.12566
9
[10] Soleimani, H., Ghaderi, H., Tsai, P. W., Zarbakhshnia, N., & Maleki, M. Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization. Journal of Cleaner Production. 2020; 249: 119428.
10
[11] Zhu, W., & Tianyu, L. A Novel Multi-Objective Scheduling Method for Energy Based Unrelated Parallel Machines With Auxiliary Resource Constraints. IEEE Access.2019; 7: 168688-168699.
11
[12] Moon, J. Y., Shin, K., & Park, J. Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency. The International Journal of Advanced Manufacturing Technology. 2013; 68(1-4): 523-35.
12
[13] Ding, J. Y., Song, S., Zhang, R., Chiong, R., & Wu, C. Parallel machine scheduling under time-of-use electricity prices: New models and optimization approaches. IEEE Transactions on Automation Science and Engineering. 2015; 13(2): 1138-54.
13
[14] Che, A., Zhang, S., & Wu, X. Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. Journal of Cleaner Production. 2017; 156: 688-97.
14
[15] Cheng, J., Chu, F., & Zhou, M. An improved model for parallel machine scheduling under time-of-use electricity price. IEEE Transactions on Automation Science and Engineering. 2017; 15(2): 896-9.
15
[16] Abikarram, J. B., McConky, K., & Proano, R. Energy cost minimization for unrelated parallel machine scheduling under real time and demand charge pricing. Journal of Cleaner Production. 2019; 208: 232-42.
16
[17] Saberi-Aliabad, H., Reisi-Nafchi, M., & Moslehi, G. Energy-efficient scheduling in an unrelated parallel-machine environment under time-of-use electricity tariffs. Journal of Cleaner Production.2020;249: 119393.
17
[18] Kurniawan, B. Mathematical Models of Energy-Conscious Bi-Objective Unrelated Parallel Machine Scheduling. Jurnal Teknik Industri.2020; 21(2): 115-125.
18
[19] Wang, S., Wang, X., Yu, J., Ma, S., & Liu, M. Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan. Journal of Cleaner Production. 2018; 193: 424-40.
19
[20] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics: Elsevier; 1979. p. 287-326.
20
[21] Ehrgott, M., & Gandibleux, X. Multiobjective combinatorial optimization—theory, methodology, and applications. Multiple criteria optimization: State of the art annotated bibliographic surveys: Springer; 2003. p. 369-444.
21
[22] Coello, C. A. C., Pulido, G. T., & Lechuga, M. S. Handling multiple objectives with particle swarm optimization. IEEE Transactions on evolutionary computation. 2004; 8(3): 256-79.
22
[23] Wang, W., Chen, L., Jie, J., Zhao, Y., & Zhang, J. A novel multi-objective particle swarm optimization algorithm for flow shop scheduling problems. International Conference on Intelligent Computing: Springer; 2011 .p. 24-31.
23
[24] Torabi, S. A., Sahebjamnia, N., Mansouri, S. A., & Bajestani, M. A. A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem. Applied Soft Computing. 2013; 13(12): 4750-62.
24
[25] Liao, X., Zhang, R., & Chiong, R. Multi-objective optimization of single machine scheduling with energy consumption constraints. IEEE Symposium Series on Computational Intelligence (SSCI): IEEE; 2017. p. 1-8.
25
[26] Manupati, V. K., Rajyalakshmi, G., Chan, F. T., & Thakkar, J. J. A hybrid multi-objective evolutionary algorithm approach for handling sequence-and machine-dependent set-up times in unrelated parallel machine scheduling problem. Sādhanā. 2017; 42(3): 391-403.
26
[27] Liu, Y., Liao, X., & Zhang, R. An Enhanced MOPSO Algorithm for Energy-Efficient Single-Machine Production Scheduling. Sustainability,. 2019; 11(19): 5381.
27
[28] Ulungu, E. L., Teghem, J. F. P. H., Fortemps, P. H., & Tuyttens, D. MOSA method: a tool for solving multiobjective combinatorial optimization problems. Journal of multicriteria decision analysis. 1999; 8(4): 221.
28
[29] Mansouri, S. A., Hendizadeh, S. H., & Salmasi, N. Bicriteria scheduling of a two-machine flowshop with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology. 2009; 40(11-12): 1216-26.
29
[30] Chyu, C. C., & Chang, W. S. Optimizing fuzzy makespan and tardiness for unrelated parallel machine scheduling with archived metaheuristics. The International Journal of Advanced Manufacturing Technology. 2011; 57(5-8): 763.
30
[31] Mohammadi, H., & Sahraeian, R. Bi-objective simulated annealing and adaptive memory procedure approaches to solve a hybrid flow shop scheduling problem with unrelated parallel machines. IEEE International Conference on Industrial Engineering and Engineering Management: IEEE; 2012. p. 528-32.
31
[32] Shoaardebili, N., & Fattahi, P. Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints. International Journal of Production Research. 2015; 53(3): 944-68.
32
[33] Tirkolaee, E. B., Goli, A., Hematian, M., Sangaiah, A. K., & Han, T. Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithms. Computing. 2019; 101(6): 547-70.
33
[34] Shannon, C. E. A mathematical theory of communication. The Bell system technical journal. 1948; 27(3): 379-423.
34
[35] Zhang, H., Wu, Y., Pan, R., & Xu, G. Two-stage parallel speed-scaling machine scheduling under time-of-use tariffs. Journal of Intelligent Manufacturing. 2020:1-22.
35
ORIGINAL_ARTICLE
Integrated Production and Distribution Scheduling in Mobile Facilities
Many supply chains lack flexibility and adaptability in today's competitive market, resulting in customer dissatisfaction, backorders, and several extra costs for the business. Additionally, the inability to quickly meet the customer's demands and the unnecessary transportation costs is also one of the significant challenges faced by the fixed facilities' supply chain. To address these challenges, this study analyzed the mobile facilities supply chain and the production, distribution, and delivery of goods conducted by trucks based on customer preferences. This study proposes a bi-objective mixed-integer linear programming model to ensure the mobile facilities' routing and manufacturing schedules are optimized to meet the customer's needs. Furthermore, this model minimizes production and distribution costs in the shortest amount of time. An exact decomposition algorithm based on Benders decomposition is used to find high-quality solutions in a reasonable amount of time to tackle the problem efficiently. We present several acceleration strategies for increasing the convergence rate of Benders' decomposition algorithm, including Pareto optimality cut and warm-up start. The warm-up start acceleration strategy itself is a meta-heuristic based on particle swarm optimization (PSO). Using the Benders decomposition, we demonstrate the superior accuracy of our solution methodology for large-scale cases with 10 kinds of products ordered by 30 customers using 10 mobile facilities.
https://aie.ut.ac.ir/article_83038_41c4adc06ca97dcc2dc64dec28352c2e.pdf
2021-01-01
115
132
10.22059/jieng.2021.326964.1790
Accelerated benders decomposition algorithms
Benders decomposition
Integrated Production and Routing Problem
Mobile Facilities
Mobile Facilities’ Supply Chain
Mohammad Hossein
Mahdavi
mahdavi.mohamadhossein@gmail.com
1
Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran
AUTHOR
Reza
Ramezanian
ramezanian@kntu.ac.ir
2
Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran
LEAD_AUTHOR
[1] Behzad, A. and Pirayesh, M.A., 2016. Designing supply chain network of mobile factories, 2nd international conference of industrial & systems engineering. https://civilica.com/doc/540369 (In persian)
1
[2] Adulyasak, Y., Cordeau, J.F. and Jans, R., 2015. The production routing problem: A review of formulations and solution algorithms. Computers & Operations Research, 55, pp.141-152.
2
[3] Fu, L.L., Aloulou, M.A. and Triki, C., 2017. Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows. International Journal of Production Research, 55(20), pp.5942-5957.
3
[4] Lei, C., Lin, W.H. and Miao, L., 2016. A two-stage robust optimization approach for the mobile facility fleet sizing and routing problem under uncertainty. Computers & Operations Research, 67, pp.75-89.
4
[5] Halper, R., Raghavan, S. and Sahin, M., 2015. Local search heuristics for the mobile facility location problem. Computers & Operations Research, 62, pp.210-223.
5
[6] Raghavan, S., Sahin, M. and Salman, F.S., 2019. The capacitated mobile facility location problem. European Journal of Operational Research, 277(2), pp.507-520.
6
[7] Halper, R. and Raghavan, S., 2011. The mobile facility routing problem. Transportation Science, 45(3), pp.413-434.
7
[8] Mohammadi, S., Al-e-Hashem, S.M. and Rekik, Y., 2020. An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company. International Journal of Production Economics, 219, pp.347-359.
8
[9] Lei, C., Lin, W.H. and Miao, L., 2014. A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem. European Journal of Operational Research, 238(3), pp.699-710.
9
[10] Friggstad, Z. and Salavatipour, M.R., 2011. Minimizing movement in mobile facility location problems. ACM Transactions on Algorithms (TALG), 7(3), pp.1-22.
10
[11] Singgih, I.K., 2020, June. Mobile Laboratory Routing Problem for COVID-19 Testing Considering Limited Capacities of Hospitals. In 2020 3rd International Conference on Mechanical, Electronics, Computer, and Industrial Technology (MECnIT)(pp. 80-83). IEEE.
11
[12] Low, C., Chang, C.M., Li, R.K. and Huang, C.L., 2014. Coordination of production scheduling and delivery problems with heterogeneous fleet. International Journal of Production Economics, 153, pp.139-148.
12
[13] Liu, P. and Lu, X., 2016. Integrated production and job delivery scheduling with an availability constraint. International Journal of Production Economics, 176, pp.1-6.
13
[14] Soukhal, A., Oulamara, A. and Martineau, P., 2005. Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research, 161(1), pp.32-41.
14
[15] Hassanzadeh, A., Rasti-Barzoki, M. and Khosroshahi, H., 2016. Two new meta-heuristics for a bi-objective supply chain scheduling problem in flow-shop environment. Applied soft computing, 49, pp.335-351.
15
[16] Güden, H. and Süral, H., 2019. The dynamic p-median problem with mobile facilities. Computers & Industrial Engineering.
16
[17] Demir, , Eyers, D. and Huang, Y., 2021. Competing through the last mile: Strategic 3D printing in a city logistics context. Computers & Operations Research, 131, p.105248.
17
[18] Tang, C.S., Veelenturf, L.P., 2019. The strategic role of logistics in the industry 4.0 era. Transportation Research Part E: Logistics and Transportation Review, 129, 1–11.
18
[19] Savelsbergh, M., Van Woensel, T., 2016. 50th anniversary invited article–city logistics: Challenges and opportunities. Transportation Science 50, 579–590.
19
[20] Durocher, S., Kirkpatrick, D., 2006. The steiner centre of a set of points: stability, eccentricity, and applications to mobile facility location. International Journal of Computational Geometry & Applications, 16 (04), 345–371.
20
[21] Bashiri,, Rezanezhad, M., Tavakkoli-Moghaddam, R. and Hasanzadeh, H., 2018. Mathematical modeling for a p-mobile hub location problem in a dynamic environment by a genetic algorithm. Applied Mathematical Modelling, 54, pp.151-169.
21
[22] Shahmoradi-Moghadam, H. and Schönberger, J., 2021. Joint Optimization of Production and Routing Master Planning in Mobile Supply Chains. Operations Research Perspectives, p.100187.
22
[23] Jackson M, Wiktorsson M, Bellgran M. Factory-in-a-box — Demonstrating the next
23
generation manufacturing provider. Manuf. Syst. Technol. New Front., London:
24
Springer London; 2008, p. 341–6. https://doi.org/10.1007/978-1-84800-267-8_70.
25
[24] Fox S. Reliable Autonomous Production Systems: Combining Industrial Engineering Methods and Situation Awareness Modelling in Critical Realist Design of
26
Autonomous Production Systems. Systems 2018;6:26.
27
https://doi.org/10.3390/systems6030026.
28
[25] Koren Y, Gu X, Guo W. Reconfigurable manufacturing systems: Principles, design, and future trends. Front Mech Eng 2018;13:121–36. https://doi.org/10.1007/s11465-
29
018-0483-0.
30
[26] Antzoulatos N, Castro E, Scrimieri D, Ratchev S. A multi-agent architecture for plug and produce on an industrial assembly platform. Prod Eng 2014;8:773–81.
31
https://doi.org/10.1007/s11740-014-0571-x.
32
[27] Moons S, Ramaekers K, Caris A, Arda Y. Integrating production scheduling and
33
vehicle routing decisions at the operational decision level: A review and discussion.
34
Computers and Industrial Engineering, 2017;104:224–45. https://doi.org/10.1016/j.cie.2016.12.010.
35
[28] Behzad, A., Pirayesh, M. and Ranjbar, M., 2017. Routing and Production Scheduling for a Mobile Factory. International Journal of Industrial Engineering & Production Research, 28(3), pp.299-308.
36
[29] Ivanov D, Tsipoulanidis A, Schönberger J. Erratum to: Global Supply Chain and
37
Operations Management, 2017, p. E1–E1. https://doi.org/10.1007/978-3-319-
38
24217-0_15.
39
[30] Shahmoradi-Moghadam H, Samani O, Schönberger J. A Hybrid Robust-Stochastic
40
Optimization Approach for the Noise Pollution Routing Problem with a
41
Heterogeneous Vehicle Fleet. International Conference Dynamics Logistics, 2020, p. 124–34.
42
https://doi.org/10.1007/978-3-030-44783-0_12.
43
[31] Braekers K, Ramaekers K, Van Nieuwenhuyse I. The vehicle routing problem: State of
44
the art classification and review. Computers and Industrial Engineering, 2016;99:300–13.
45
https://doi.org/10.1016/j.cie.2015.12.007.
46
[32] Fazli Besheli, B., Jahan, A. (2018). 'multi-item multi-objective optimization-location dynamic model with reliability', Advances in Industrial Engineering, 52(3), pp. 445-458. doi: 10.22059/jieng.2019.226472.1314
47
[33] Demaine, E.D., Hajiaghayi, M., Mahini, H., Sayedi-Roshkhar, A.S., Oveisgharan, S. and Zadimoghaddam, M., 2009. Minimizing movement. ACM Transactions on Algorithms (TALG), 5(3), pp.1-30.
48
[34] Mohammadi, S., Al-e-Hashem, S.M. and Rekik, Y., 2020. An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company. International Journal of Production Economics, 219, pp.347-359.
49
[35] Sağlam, Ü. and Banerjee, A., 2018. Integrated multiproduct batch production and truck shipment scheduling under different shipping policies. Omega, 74, pp.70-81.
50
[36] Karaoğlan, İ. and Kesen, S.E., 2017. The coordinated production and transportation scheduling problem with a time-sensitive product: a branch-and-cut algorithm. International Journal of Production Research, 55(2), pp.536-557.
51
[37] Benders, F. (1962). Partitioning procedures for solving mixed-variables programming
52
problems. Numerische Mathematik, 4(1), 238–252
53
[38] De Camargo, Ricardo Saraiva, Gilberto de Miranda Jr, and Henrique Pacca L. Luna. "Benders decomposition for hub location problems with economies of scale." Transportation Science1(2009): 86-97.
54
[39] Rebennack, S. “Combining sampling-based and scenario-based nested Benders
55
decomposition methods: application to stochastic dual dynamic programming,”
56
Program., 156(1–2), pp. 343–389 (2016).
57
[40] Magnanti, T.L. and Wong, R.T., 1981. Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3), pp.464-484.
58
[41] Watson, F.R. and Rogers, D.F., 2006. Pareto-Optimality of the Balinski Cut for the Uncapacitated Facility Location Problem.
59
[42] Geoffrion, A.M., 2010. Lagrangian relaxation for integer programming. In 50 Years of Integer Programming 1958-2008(pp. 243-281). Springer, Berlin, Heidelberg.
60
[43] O’Kelly, M.E., Luna, H.P.L., De Camargo, R.S. and De Miranda, G., 2015. Hub location problems with price sensitive demands. Networks and Spatial Economics, 15(4), pp.917-945.
61
[44] Contreras, I., Cordeau, J.F. and Laporte, G., 2011. Benders decomposition for large-scale uncapacitated hub location. Operations Research, 59(6), pp.1477-1490.
62
[45] Easwaran, G. and Üster, H., 2010. A closed-loop supply chain network design problem with integrated forward and reverse channel decisions. IIE Transactions, 42(11), pp.779-792.
63
[46] Eberhart, R. and Kennedy, J., 1995, November. Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks(Vol. 4, pp. 1942-1948). Citeseer.
64
[47] A. C. Coello, G. T. Pulido and M. S. Lechuga, "Handling multiple objectives with particle swarm optimization," IEEE Transactions on Evolutionary Computation, vol. 8, no. 3, pp. 256-279, June 2004, doi: 10.1109/TEVC.2004.826067.
65
[48] Gong, Y.J., Zhang, J., Liu, O., Huang, R.Z., Chung, H.S.H. and Shi, Y.H., 2011. Optimizing the vehicle routing problem with time windows: A discrete particle swarm optimization approach. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(2), pp.254-267.
66