Solving practical waste collection with time windows in an urban area

  • Authors

    • Abdulwahab Almutairi School of Mathematics, Qassim University
    2020-12-25
    https://doi.org/10.14419/ijasp.v9i1.31188
  • ALNS, Iterated Greedy, Time Window, Waste Collection.
  • In logistics, several algorithms can be implemented in order to solve the problems of the vehicle routing with variants in order to find near-optimal solutions. Waste Collection can be considered as an essential logistic activity within any area or city. This kind of paper is aimed to implement Iterated greedy (IG) and Adaptive Large Neighborhood Search (ALNS) to solve waste collection vehicle routing problem with time windows on a real-case study. The idea is to generate an efficient way to collect waste problems in an area located in Riyadh, Saudi Arabia. Moreover, generating a route plays a significant role in terms of serving all customers’ demands who have own different time windows of receiving goods. Also, the performance of the proposed algorithms according to all instances is examined and minimizing the total costs and meeting all constraints that related to capacity, time windows, and others. To evaluate the execution of the presented algorithms, the computational results showed essential improvements, and also ALNS algorithm generates reasonable solutions in terms of total costs and a reasonable amount of time, when compared to other algorithms.

     

     

  • References

    1. [1] Almutairi A. (2020). Combined Nearest Greedy algorithm with randomised algorithm to solve waste collection problem. International Journal of Statistics and probability. Vol.9,No.3.DOI:10.5539/ijsp.v9n3p66. http://www.ccsenet.org/journal/index.php/ijsp/article/view/0/42581. https://doi.org/10.5539/ijsp.v9n3p66.

      [2] Almutairi A. (2018). Solving capacitated vehicle routing problem by iterated greedy algorithm. Journal of Natural Science and Maths. JNM:2018 MATH-02

      [3] Almutairi A. (2018). Using randomization into iterated greedy algorithm in order to solve capacitated vehicle routing problem. Journal of Natural Science and Maths. JNM: 2018 MATH-03.

      [4] Braaten, S., Gjonnes, O., Hvattum, L, M., tirade, G., (2017). Heuristic for the robust vehicle routing problem with time windows. Expert system with applications. 77(2017) 136-147. https://doi.org/10.1016/j.eswa.2017.01.038.

      [5] Buhrkala, K., Larsena, A., Ropkea, S., (2012). The waste collection vehicle routing problem with time windows in a city logistics context. The Seventh International Conference on City Logistics. Procedia - Social and Behavioral Sciences 39 (2012) 241 – 254. https://doi.org/10.1016/j.sbspro.2012.03.105.

      [6] Changshi Liu, C. Kou, G., Zhou, X., Peng, Y., Sheng, H., Alsaadi, F. 2019. Time-dependent vehicle routing problem with time windows of city logistics with a congestion avoidance approach. Knowledge-Based Systems.

      [7] Chena. J., Shic, J., 2019. A multi-compartment vehicle routing problem with time windows for urban distribution – A comparison study on particle swarm optimization algorithms. Computers & Industrial Engineering 133 (2019) 95–106. https://doi.org/10.1016/j.cie.2019.05.008.

      [8] Demir, E., Bektas, T., Laporte, G., (2012). An adaptive large neighbourhood search heuristic for the pollution-routing problem. European Journal of operational research 223(2012)364-359. https://doi.org/10.1016/j.ejor.2012.06.044.

      [9] Dantzig, G, B., Ramser, J, H. (1959). The truck dispatching problem, management science, Vol. 6, No. 1, pp. 80-91.
      https://doi.org/10.1287/mnsc.6.1.80.

      [10] El-sherbeny, N., (2010). Vehicle routing with time windows: an overview of exact, heuristic and metaheuristic methods. Journal of king Saud University (science). 2010. 22, 123-131. https://doi.org/10.1016/j.jksus.2010.03.002.

      [11] Faccio, M., Persona, A., Zanin. G., (2011). Waste collection multi objective model with real time traceability data. Waste management. 31 (2011) 2391-2405. https://doi.org/10.1016/j.wasman.2011.07.005.

      [12] Gu, W., Cattaruzza, D., Ogier, M., Semet, F., adaptive large neighbourhood search for the commodity constrained split delivery VRP. Computer and operations research 112(2019) 104761. https://doi.org/10.1016/j.cor.2019.07.019.

      [13] Kim, B., Kim, S., Sahoob, S. (2006). Waste collection vehicle routing problem with time windows. Computers & Operations Research 33 (2006) 3624–3642. https://doi.org/10.1016/j.cor.2005.02.045.

      [14] Liu, X., Laporte, G., Chen, Y., He, R., (2017). An adaptive large neighbourhood search metaheuristic for agile satellite scheduling with time-dependent transition time. Computer and operations research. S0305-0548(17)30097-7. https://doi.org/10.1016/j.cor.2017.04.006.

      [15] Latiffianti, E., Siswanto, N., Firmandani, R, A. (2017). Split delivery vehicle routing problem with time windows: a case study. International conference on industrial and system engineering (IConISE). https://doi.org/10.1088/1757-899X/337/1/012012.

      [16] Miranda, D, M., Conceicao, S, V., (2016). The vehicle routing problem with hard time windows and stochastic travel and service time. Expert system with application 64 (2016) 104-116. https://doi.org/10.1016/j.eswa.2016.07.022.

      [17] Mattos Ribeiro, G., Laportea, G., (2012). An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computer & operations research. 39 (3) 728-735. https://doi.org/10.1016/j.cor.2011.05.005.

      [18] Nghia, N, H., Hieu, N, M., Linh, N, T, T., (2016). Solving practical vehicle routing problem with time windows (VRPTW)- a case study of ICD time son (Vietnam).

      [19] Ruiz R, Stutzle T. An Iterated Greedy Algorithm for the Flowshop Problem with Sequence Dependent Setup Times. The 6th Metaheuristics International Conference, 2005. 817–823.

      [20] Ruiz R, Stutzle T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Euro Journal of Opera Res, 2007. 177, 2033–2049. https://doi.org/10.1016/j.ejor.2005.12.009.

      [21] Ropke, S., Pisinger, D., 2006. An adaptive large neighbourhood search heuristic for the pickup and delivery problem with time windows. Transportation Science. 40(4), 455-472. https://doi.org/10.1287/trsc.1050.0135.

      [22] Tas, D., Dellaert, N., Woensel, T., De Kok, T., (2013). Vehicle routing problem with stochastic travel times including soft time windows and service costs. Computer & operations research 40 (2013) 214-224. https://doi.org/10.1016/j.cor.2012.06.008.

      [23] Zhena, L., Maa, C., Wanga, K, Xiaoa, L., Zhangc, W., (2020). Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Research Part E 135 (2020) 101866. https://doi.org/10.1016/j.tre.2020.101866.

  • Downloads