Hybrid Variable Neighborhood Search for solving school bus-driver problem with resource constraints

• Autorzy: Ban Ha-Bang , Nguyen Hong-Phuong , Pham Dang-Hai

Identyfikatory

DOI

10.7494/csci.2023.24.3.4367

• Języki publikacji: EN

Abstrakty

EN

The school bus-priver problem with resource constraints (SBDP-RC) is an optimization problem with many practical applications. In the problem, several vehicles are prepared to pick a number of pupils in which the total resources of all vehicles are lower than a predefined value. The aim is to find a schedule that minimizes the sum of the pupils’ waiting times. The problem is NP-hard in the general case. In this paper, to solve the problem. After this, the post phase improves the solution by a general variable neighborhood search (GVNS) with a random neighborhood search combined with shaking technique. The proposed metaheuristic hybridization algorithm is tested on a benchmark to show its efficiency. The results show that the algorithm receives good feasible solutions fast. In many cases, better solutions can be found compared to previous metaheuristic algorithms.

Słowa kluczowe

EN

SBDP-RC; metaheuristic; VNS

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2023
• Tom: T. 24 (3)
• Strony: 297--325
• Opis fizyczny: Bibliogr. 19 poz., rys., tab., wykr.

Twórcy

autor

Ban Ha-Bang

• Hanoi University of Science and Technology, School of Information and CommunicationTechnology, Hanoi, Vietnam

autor

Nguyen Hong-Phuong

• Hanoi University of Science and Technology, School of Information and CommunicationTechnology, Hanoi, Vietnam

autor

Pham Dang-Hai

• Hanoi University of Science and Technology, School of Information and CommunicationTechnology, Hanoi, Vietnam

Bibliografia

• [1] Ajam M., Akbari V., Salman F.S.: Minimizing latency in post-disaster roadclearance operations, European Journal of Operational Research, vol. 277(3),pp. 1098–1112, 2019. doi: 10.1016/j.ejor.2019.03.024.
• [2] Ban H.B.: A GRASP+VND Algorithm for the Multiple Traveling RepairmanProblem with Distance Constraints, Journal of Computer Science and Cybernetics, vol. 33(3), pp. 272–288, 2017. doi: 10.15625/1813-9663/33/3/10511.
• [3] Ban H.B.: A RVND+ILS Metaheuristic to Solve the Delivery Man Problem withTime Windows. In: A. Tagarelli, H. Tong (eds.), Computational Data and Social Networks, pp. 63–69, Springer International Publishing, Cham, 2019.
• [4] Ban H.B., Nguyen D.N.: An effective GRASP+VND metaheuristic for thek-Minimum Latency Problem. In: 2016 IEEE RIVF International Conferenceon Computing & Communication Technologies, Research, Innovation, and Vision for the Future (RIVF), pp. 31–36, 2016. doi: 10.1109/RIVF.2016.7800265.
• [5] Ban H.B., Nguyen D.N.: A meta-heuristic algorithm combining between tabuand variable neighborhood search for the minimum latency problem, Fundamenta Informaticae, vol. 156(1), pp. 21–41, 2017.
• [6] Ban H.B., Nguyen D.N.: Metaheuristic for the Traveling Repairman Problemwith Time Window Constraints. In:2019 IEEE-RIVF International Conference on Computing and Communication Technologies (RIVF), pp. 1–6, 2019.doi: 10.1109/RIVF.2019.8713655.
• [7] Bruni M., Beraldi P., Khodaparasti S.: A hybrid reactive GRASP heuristic for therisk-aversek-traveling repairman problem with profits, Computers & Operations Research, vol. 115, 104854, 2020. doi: 10.1016/j.cor.2019.104854.
• [8] Feo T.A., Resende M.G.C.: Greedy randomized adaptive search procedures, Journal of Global Optimization, vol. 6, pp. 109–133, 1995.
• [9] Ke L., Feng Z.: A two-phase metaheuristic for the cumulative capacitated vehiclerouting problem, Computers&Operations Research, vol. 40(2), pp. 633–638,2013. doi: 10.1016/j.cor.2012.08.020.
• [10] Lu Y., Benlic U., Wu Q., Peng B.: Memetic algorithm for the multiple traveling repairman problem with profits, Engineering Applications of Artificial Intelligence, vol. 80, pp. 35–47, 2019.
• [11] Luo Z., Qin H., Lim A.: Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints, European Journal of Operational Research, vol. 234(1), pp. 49–60, 2014.
• [12] Martin O., Otto S.W., Felten E.W.: Large-Step Markov Chains for the Traveling Salesman Problem, Complex Systems, vol. 5, pp. 299–326, 1991.
• [13] Mladenovic N., Hansen P.: Variable neighborhood search, Computers & Operations Research, vol. 24(11), pp. 1097–1100, 1997.
• [14] Mladenovic N., Urosevic D., Hanafi S.: Variable neighborhood search for the travelling deliveryman problem, 4OR, vol. 11, pp. 57–73, 2013.
• [15] NEO, 2013. http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances.
• [16] Nucamendi-Guilln S., Martnez-Salazar I., Angel-Bello F., Moreno-Vega J.M.:A mixed integer formulation and an efficient metaheuristic procedure for the k-Travelling Repairmen Problem, Journal of the Operational Research Society,vol. 67(8), pp. 1121–1134, 2016. doi: 10.1057/jors.2015.113.
• [17] Ome Ezzine I., Elloumi S.: Polynomial formulation and heuristic based approach for the k-travelling repairman problem, International Journal of Mathematics in Operational Research, vol. 4(5), pp. 503–514, 2012.
• [18] Pei J., Mladenovic N., Urosevic D., Brimberg J., Liu X.: Solving the traveling repairman problem with profits: A novel variable neighborhood search approach, Information Sciences, vol. 507, pp. 108–123, 2020.
• [19] Will T.G.:Extremal results and algorithms for degree sequences of graphs, University of Illinois at Urbana-Champaign, 1993.