Time Window and Location Based Clustered Routing with Big and Distributed Data

Mehmet Fatih Yüce; Ali Gunes; Metin Zontul; Tuğba Altintas

doi:doi:10.11648/j.ie.20180202.11

| Peer-Reviewed

Time Window and Location Based Clustered Routing with Big and Distributed Data

Mehmet Fatih Yüce, Ali Gunes, Metin Zontul, Tuğba Altintas

Published in Industrial Engineering (Volume 2, Issue 2)

Received: 14 September 2018 Accepted: 12 October 2018 Published: 7 November 2018

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

In this paper, a novel vehicle routing algorithm will be presented. Proposed method will be based on “time windows-based clustering” and “location-based clustering”, applied in reversable consecutive order. The method partitions and models the solution space with machine learning technologies, resulting in a better performance for time window and geospatial clustering calculations. Routing process, on the other hand, will be built upon already present open source tools, giving it usability, applicability, manageability, and integration perspectives. The process combines “cluster+cluster+route” units with post process enhancements. Previous works on location-based clustering are proved to be successful, albeit with some disadvantages. On the other hand, routing algorithms have mostly implemented time window calculations as second-class citizens. In this method, time window is a major ingredient of the modelling process. This paper will also differs from some other combinatoric methods used in literature. A history and general description of used methods and tools will also be provided. It is shown that the algorithm can generate good results, some of which are the best values in the recorded literature so far. The method is applied on a big data platform. Horizontal scaling and distributed processing capabilities with the state-of-the-art tooling on such systems are also described.

Published in	Industrial Engineering (Volume 2, Issue 2)
DOI	10.11648/j.ie.20180202.11
Page(s)	42-51
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Two Step Clustering, Vehicle Routing, CVRP, VRPTW, Big Data

References

[1]	A. J. Hoffman, J. Wolfe, R. S. Garfinkel, D. S. Johnson, C. H. Papadimitriou, P. C. Gilmore and B. L. Golden, (1986). "The traveling salesman problem: a guided tour of combinatorial optimization," J. Wiley & Sons.
[2]	M. M. Flood, (1955). "The Traveling-Salesman Problem," J. Opns. Res. Soc.Amt. 4, pp. 61-75.
[3]	L. Zambito, (2006)."The traveling salesman problem: a comprehensive survey," in Project for CSE 4080.
[4]	Dantzig, G. B. and Ramser, J. H., (1959)."The Truck Dispatching Problem," Management Science, 6(1), p. 80–91.
[5]	S. N. Kumar and R. Panneerselvam, (2012). "A survey on the vehicle routing problem and its variants," Intelligent Information Management, 4(3), p. 66.
[6]	D. Cattaruzza, N. Absi, D. Feillet and J. González-Feliu, (2017)."Vehicle routing problems for city logistics," EURO Journal on Transportation and Logistics, vol. 6, no. 1, pp. 51-79.
[7]	M. Granada, (2016). "Literature Review On The Vehicle Routing Problem In The Green Transportation Context," revista. luna. azúl, 42, pp. 362-387.
[8]	T. K. Ralphs, L. Kopman, W. R. Pulleyblank and L. E. Trotter, (2003)."On the capacitated vehicle routing problem," Mathematical programming, 94(2-3), pp. 343-359.
[9]	D. Vigo, (1996). "A heuristic algorithm for the asymmetric capacitated vehicle routing problem," European Journal of Operational Research, 89(1), pp. 108-126.
[10]	H. A. Eiselt, M. Gendreau and G. Laporte, (1995). "Arc routing problems, part II: The rural postman problem," Operations research, 43(3), pp. 399-414.
[11]	R. Baldacci, E. Bartolini and G. Laporte, (2010)."Some applications of the generalized vehicle routing problem," Journal of the Operational Research Society, 61(7), pp. 1072-1077.
[12]	I. Kara and T. Bektas, (2003)."Integer linear programming formulation of the generalized vehicle routing problem," in EURO/INFORMS Joint International Meeting, Istanbul.
[13]	O. Bräysy and M. Gendreau, (2005)."Vehicle routing problem with time windows, Part I: Route construction and local search algorithms," Transportation science, 39(1), pp. 104-118.
[14]	B. Çatay, (2010)."A new saving-based ant algorithm for the vehicle routing problem with simultaneous A. I. Savran, E. Musaoglu, M. F. Yuce and E. Yesil, (2014). "RouteArt: A new framework for vehicle routing problem with pickup and delivery using heuristic bubble algorithm," Computational Intelligence and Informatics (CINTI), 2014 IEEE 15th International Symposium on, pp. 91-96.
[15]	A. I. Savran, E. Musaoglu, M. F. Yuce and E. Yesil, (2014). "RouteArt: A new framework for vehicle routing problem with pickup and delivery using heuristic bubble algorithm," Computational Intelligence and Informatics (CINTI), 2014 IEEE 15th International Symposium on, pp. 91-96.
[16]	J. F. Cordeau and G. Laporte, (2003). "The dial-a-ride problem (DARP): Variants, modeling issues and algorithms," Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2), pp. 89-101.
[17]	T. G. Crainic, G. Perboli, S. Mancini and R. Tadei, (2010)."Two-echelon vehicle routing problem: a satellite location analysis," Procedia-Social and Behavioral Sciences, 2(3), pp. 5944-5955.
[18]	J. Gonzalez-Feliu, G. Perboli, R. Tadei and D. Vigo, (2008)."The two-echelon capacitated vehicle routing problem," [Online]. Available: https://halshs.archives-ouvertes.fr/halshs-00879447/.
[19]	J. Crispim and J. Brandão, (2005)."Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls," Journal of the Operational Research Society, 56(11), pp. 1296-1302.
[20]	J. Jemai, M. Zekri and K. Mellouli, (2012)."An NSGA-II algorithm for the green vehicle routing problem," in In European Conference on Evolutionary Computation in Combinatorial Optimization.
[21]	G. Laporte, M. Desrochers and Y. Nobert, (1984)."Two exact algorithms for the distance‐constrained vehicle routing problem," Networks, 14(1), pp. 161-172.
[22]	G. Nagy and S. Salhi, (2007)."Location-routing: Issues, models and methods," European Journal of Operational Research, 177(2), pp. 649-672.
[23]	A. I. Savran, E. Musaoglu, C. Yildiz and M. F. Yuce, (2015)."An efficient solution to Location-Routing Problems via a two-phase heuristic bubble approach," Advanced Logistics and Transport (ICALT), 2015 4th International Conference on, pp. 169-174.
[24]	Ç. Koç, T. Bektaş, O. Jabali and G. Laporte, (2016)."Thirty years of heterogeneous vehicle routing," European Journal of Operational Research, vol. 249, no. 1, pp. 1-21.
[25]	A. M. J. E. J. O. &. L. G. Froger, (2018)."Modeling and solving the electric vehicle routing problem with nonlinear charging functions and capacitated charging stations.," ODYSSEUS.
[26]	Z. J. Czech and P. Czarnas, (2002). "A parallel simulated annealing for the vehicle routing problem with time windows," in Proc. 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain.
[27]	M. F. Yuce, E. Musaoglu and A. Gunes, (2016)."Enhancing heuristic bubble algorithm with simulated annealing," Cogent Business & Management, vol. 3, no. 1.
[28]	A. Sakalli, (2013)."Heuristic bubble algorithm for a linehaul routing problem: An extension of a vehicle routing problem with pickup and delivery," in Computational Intelligence and Informatics (CINTI), 2013 IEEE 14th International Symposium on. IEEE.
[29]	M. M. Solomon, (1987). "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations research, 35(2), p. 254-265.
[30]	J. Brandão, (2017)."Iterated Local Search Algorithm for the Vehicle Routing Problem with Backhauls and Soft Time Windows," ISEG-Lisbon School of Economics and Management, REM, Universidade de Lisboa., no. 10.
[31]	G. Desaulniers, F. Errico, S. Irnich and M. Schneider, (2016)."Exact algorithms for electric vehicle-routing problems with time windows," Operations Research, vol. 64, no. 6, pp. 1388-1405.
[32]	F. Errico, G. Desaulniers, M. Gendreau, W. Rei and L. M. Rousseau, (2018)."The vehicle routing problem with hard time windows and stochastic service times," EURO Journal on Transportation and Logistics, vol. 7, no. 3, pp. 223-251.
[33]	U. M. Yildirim and B. Çatay, (2012). "A time-based pheromone approach for the ant system.," Optimization Letters 6.6, pp. 1081-1099.
[34]	J. E. Beasley, (1983). "Route first—cluster second methods for vehicle routing," Omega, 11(4), pp. 403-408.
[35]	R. Dondo and Cerdá, (2007)."A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows," European Journal of Operational Research, 176(3), pp. 1478-1507.
[36]	G. S. Almasi and A. Gottlieb, (1994).Highly parallel computing - 2nd ed., Redwood City, CA, USA: Benjamin-Cummings Publishing Co., Inc..
[37]	D. E. Culler, J. P. Singh and A. Gupta, (1999).Parallel computer architecture: a hardware/software approach., Gulf Professional Publishing.
[38]	C. Lynch, (2008). "Big data: How do your data grow?," Nature, pp. 28-29.
[39]	A. Holmes, (2014).Hadoop in practice, Second Edition, Manning Publications Co.
[40]	Boyd, D. and Crawford, K., (2012). "Critical questions for big data: Provocations for a cultural, technological, and scholarly phenomenon," in Information, communication & society, pp. 662-679.
[41]	J. R. Mashey, (1997)." Big Data and the next wave of infraS-tress," in Computer Science Division Seminar.
[42]	D. Laney, (2001)."3D data management: Controlling data volume, velocity and variety," META Group Research Note, 6, p. 70.
[43]	K. Shvachko, (2010)."The hadoop distributed file system.," in Mass Storage Systems and Technologies (MSST), 2010 IEEE 26th Symposium on. IEEE.
[44]	S. Ghemawat, H. Gobioff and S. T. Leung, (2003). "The Google file system," ACM SIGOPS operating systems review, vol. 37, no. 5, pp. 29-43.
[45]	J. Dean and S. Ghemawat, (2004)."MapReduce: simplified data processing on large clusters," 28 October 2004. [Online]. Available: http://research.google.com/archive/mapreduce.html.
[46]	Apache Yazılım Vakfı, (2018). "Welcome to Apache Hadoop!," [Online]. Available: http://hadoop.apache.org/. [Accessed 03 10 2018].
[47]	T. White, (2015). "Hadoop: The Definitive Guide 4th Edition" , pp. 3-15.
[48]	M. Cafarella and D. Cutting, (2004). "Building Nutch: Open Source," Magazine Queue - Search Engines Volume 2 Issue 2, p. 54.
[49]	O. O’Malley, (2008)."Terabyte sort on apache hadoop". [Online]. Available: http://sortbenchmark. org/Yahoo-Hadoop.
[50]	"Sorting 1PB with MapReduce," (2008). [Online]. Available: https://googleblog.blogspot.com.tr/2008/11/sorting-1pb-with-mapreduce.html. [Accessed 3 10 2018].
[51]	"Distributions and Commercial Support,"(2018). [Online]. Available: https://wiki.apache.org/hadoop/Distributions%20and%20Commercial%20Support. [Accessed 3 10 2018].
[52]	J. Li, S. Mehrotra and W. Zhu, (2013). "Prajna: Cloud Service and Interactive Big Data Analytics,". [Online].
[53]	"Cloudera Customers," (2018). Available: http://www.cloudera.com/customers.html. [Accessed 3 10 2018].
[54]	S. P. Apache Yazılım Vakfı, (2018)."Clustering - RDD-based API," [Online]. Available: http://spark.apache.org/docs/latest/mllib-clustering.html#k-means. [Accessed 3 10 2018].
[55]	B. Bahmani, B. Moseley, A. Vattani, R. Kumar and S. Vassilvitskii, (2012)."Scalable k-means++," Proceedings of the VLDB Endowment, 5(7), pp. 622-633.
[56]	D. Arthur and S. Vassilvitskii, (2007)."k-means++: The advantages of careful seeding," In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics., pp. 1027-1035.
[57]	J. Homberger and H. Gehring, (2018). "Extended Solomon's VRPTW instances.," 26 09 2018. [Online]. Available: https://www.sintef.no/globalassets/project/top/vrptw/homberger/1000/homberger_1000_customer_instances.zip.
[58]	S. Schröder, (2018). "jsprit-project," [Online]. Available: http://jsprit.github.io/. [Accessed 03 10 2018].
[59]	J. Schuijbroek, R. C. Hampshire and W. J. Van Hoeve, (2017). "Inventory rebalancing and vehicle routing in bike sharing systems," European Journal of Operational Research, vol. 257, no. 3, pp. 992-1004.
[60]	B. T., D. E. and L. G., (2016). "Green Vehicle Routing," Green transportation logistics Springer, Cham., pp. 243-265.
[61]	E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal and A. Subramanian, (2017). " New benchmark instances for the capacitated vehicle routing problem," European Journal of Operational Research, vol. 257, no. 3, pp. 845-858.

Cite This Article

Plain Text BibTeX RIS

APA Style

Mehmet Fatih Yüce, Ali Gunes, Metin Zontul, Tuğba Altintas. (2018). Time Window and Location Based Clustered Routing with Big and Distributed Data. Industrial Engineering, 2(2), 42-51. https://doi.org/10.11648/j.ie.20180202.11

Copy | Download

ACS Style

Mehmet Fatih Yüce; Ali Gunes; Metin Zontul; Tuğba Altintas. Time Window and Location Based Clustered Routing with Big and Distributed Data. Ind. Eng. 2018, 2(2), 42-51. doi: 10.11648/j.ie.20180202.11

Copy | Download

AMA Style

Mehmet Fatih Yüce, Ali Gunes, Metin Zontul, Tuğba Altintas. Time Window and Location Based Clustered Routing with Big and Distributed Data. Ind Eng. 2018;2(2):42-51. doi: 10.11648/j.ie.20180202.11

Copy | Download

@article{10.11648/j.ie.20180202.11,
  author = {Mehmet Fatih Yüce and Ali Gunes and Metin Zontul and Tuğba Altintas},
  title = {Time Window and Location Based Clustered Routing with Big and Distributed Data},
  journal = {Industrial Engineering},
  volume = {2},
  number = {2},
  pages = {42-51},
  doi = {10.11648/j.ie.20180202.11},
  url = {https://doi.org/10.11648/j.ie.20180202.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ie.20180202.11},
  abstract = {In this paper, a novel vehicle routing algorithm will be presented. Proposed method will be based on “time windows-based clustering” and “location-based clustering”, applied in reversable consecutive order. The method partitions and models the solution space with machine learning technologies, resulting in a better performance for time window and geospatial clustering calculations. Routing process, on the other hand, will be built upon already present open source tools, giving it usability, applicability, manageability, and integration perspectives. The process combines “cluster+cluster+route” units with post process enhancements. Previous works on location-based clustering are proved to be successful, albeit with some disadvantages. On the other hand, routing algorithms have mostly implemented time window calculations as second-class citizens. In this method, time window is a major ingredient of the modelling process. This paper will also differs from some other combinatoric methods used in literature. A history and general description of used methods and tools will also be provided. It is shown that the algorithm can generate good results, some of which are the best values in the recorded literature so far. The method is applied on a big data platform. Horizontal scaling and distributed processing capabilities with the state-of-the-art tooling on such systems are also described.},
 year = {2018}
}

Copy | Download

TY - JOUR
T1 - Time Window and Location Based Clustered Routing with Big and Distributed Data
AU - Mehmet Fatih Yüce
AU - Ali Gunes
AU - Metin Zontul
AU - Tuğba Altintas
Y1 - 2018/11/07
PY - 2018
N1 - https://doi.org/10.11648/j.ie.20180202.11
DO - 10.11648/j.ie.20180202.11
T2 - Industrial Engineering
JF - Industrial Engineering
JO - Industrial Engineering
SP - 42
EP - 51
PB - Science Publishing Group
SN - 2640-1118
UR - https://doi.org/10.11648/j.ie.20180202.11
AB - In this paper, a novel vehicle routing algorithm will be presented. Proposed method will be based on “time windows-based clustering” and “location-based clustering”, applied in reversable consecutive order. The method partitions and models the solution space with machine learning technologies, resulting in a better performance for time window and geospatial clustering calculations. Routing process, on the other hand, will be built upon already present open source tools, giving it usability, applicability, manageability, and integration perspectives. The process combines “cluster+cluster+route” units with post process enhancements. Previous works on location-based clustering are proved to be successful, albeit with some disadvantages. On the other hand, routing algorithms have mostly implemented time window calculations as second-class citizens. In this method, time window is a major ingredient of the modelling process. This paper will also differs from some other combinatoric methods used in literature. A history and general description of used methods and tools will also be provided. It is shown that the algorithm can generate good results, some of which are the best values in the recorded literature so far. The method is applied on a big data platform. Horizontal scaling and distributed processing capabilities with the state-of-the-art tooling on such systems are also described.
VL - 2
IS - 2
ER -

Copy | Download

Author Information

Mehmet Fatih Yüce

Department of Computer Engineering, Istanbul Aydin University, Istanbul, Turkey
Ali Gunes

Department of Computer Engineering, Istanbul Aydin University, Istanbul, Turkey
Metin Zontul

Department of Computer Engineering, Istanbul Arel University, Istanbul, Turkey
Tuğba Altintas

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Mehmet Fatih Yüce, Ali Gunes, Metin Zontul, Tuğba Altintas. (2018). Time Window and Location Based Clustered Routing with Big and Distributed Data. Industrial Engineering, 2(2), 42-51. https://doi.org/10.11648/j.ie.20180202.11

Copy | Download

ACS Style

Mehmet Fatih Yüce; Ali Gunes; Metin Zontul; Tuğba Altintas. Time Window and Location Based Clustered Routing with Big and Distributed Data. Ind. Eng. 2018, 2(2), 42-51. doi: 10.11648/j.ie.20180202.11

Copy | Download

AMA Style

Mehmet Fatih Yüce, Ali Gunes, Metin Zontul, Tuğba Altintas. Time Window and Location Based Clustered Routing with Big and Distributed Data. Ind Eng. 2018;2(2):42-51. doi: 10.11648/j.ie.20180202.11

Copy | Download

@article{10.11648/j.ie.20180202.11,
  author = {Mehmet Fatih Yüce and Ali Gunes and Metin Zontul and Tuğba Altintas},
  title = {Time Window and Location Based Clustered Routing with Big and Distributed Data},
  journal = {Industrial Engineering},
  volume = {2},
  number = {2},
  pages = {42-51},
  doi = {10.11648/j.ie.20180202.11},
  url = {https://doi.org/10.11648/j.ie.20180202.11},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ie.20180202.11},
  abstract = {In this paper, a novel vehicle routing algorithm will be presented. Proposed method will be based on “time windows-based clustering” and “location-based clustering”, applied in reversable consecutive order. The method partitions and models the solution space with machine learning technologies, resulting in a better performance for time window and geospatial clustering calculations. Routing process, on the other hand, will be built upon already present open source tools, giving it usability, applicability, manageability, and integration perspectives. The process combines “cluster+cluster+route” units with post process enhancements. Previous works on location-based clustering are proved to be successful, albeit with some disadvantages. On the other hand, routing algorithms have mostly implemented time window calculations as second-class citizens. In this method, time window is a major ingredient of the modelling process. This paper will also differs from some other combinatoric methods used in literature. A history and general description of used methods and tools will also be provided. It is shown that the algorithm can generate good results, some of which are the best values in the recorded literature so far. The method is applied on a big data platform. Horizontal scaling and distributed processing capabilities with the state-of-the-art tooling on such systems are also described.},
 year = {2018}
}

Copy | Download