Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Towards solving heterogeneous fleet vehicle routing problem with time windows and additional constraints: real use case study

, , ,

DOI: http://dx.doi.org/10.15439/2016F317

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 725–728 ()

Full text

Abstract. In advanced logistics systems, there is a need for complex optimization of goods transport that would allow for cost reduction. During past decades, several theoretical and practical approaches to solve so called vehicle routing problem (VRP) are proposed in industry and in theoretical science. In theoretical terms, the problem of fleet optimal management is often transformed to discrete optimization problem that relies on determining the most economical transport routes for a strictly limited number of vehicles in order to deliver (or pick up) certain amount of goods to geographically distributed set of customers. However, real life transportation logistics problems generally differ from classical cases because they impose addition constraints on expected solutions to be found. Therefore research related to developing dedicated theoretical and technological solutions fitted to particular real life use case are very important. In the paper, the particular instance of the VRP problem which is an exemplification of the real-life business case is presented. Authors of the paper proposed an architecture of technological framework and theoretical approach designed to solve selected real instances of VRP class problems.

References

  1. G. B. Dantzig and J. H. Ramser "The truck dispatching problem," Management Science, vol. 6, no. 1, pp. 80–91, 1959.
  2. G. Clarke and J. Wright “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research, vol. 12, no. 4, pp. 568-581, 1964.
  3. É. D. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.-Y. Potvin, “A tabu search heuristic for the vehicle routing problem with soft time windows”, Transportation Science, vol. 31, pp. 170-186, 1997.
  4. S. C. Ho and D. Haugland, “A tabu search heuristic for the vehicle routing problem with time windows and split deliveries”, Computers & Operations Research, vol. 31, no. 12, pp. 1947-1964, 2004.
  5. E. Osaba and F. Díaz, "Comparison of a memetic algorithm and a tabu search algorithm for the Traveling Salesman Problem," In: FedCSIS. 2012, pp. 131-136.
  6. L. M. Gambardella, E. Taillard and G. Agazzi, "MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows" , In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization McGraw-Hill, London, UK, pp. 63-76, 1999.
  7. M. Batsyn and A. Ponomarenko, "Heuristic for a Real-life Truck and Trailer Routing Problem", Procedia Computer Science vol. 31, 2014, Pages 778–792, 2nd International Conference on Information Technology and Quantitative Management, ITQM 2014.
  8. H. Akeb, A. Bouchakhchoukha, M. Hifi, "A beam search based algorithm for the capacitated vehicle routing problem with time windows". In: Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on. IEEE, 2013. pp. 329-336.
  9. J. Hurkała, "Time-Dependent Traveling Salesman Problem with Multiple Time Windows" Annals of Computer Science and Information Systems, vol. 6, pp. 71-78, 2015.
  10. R. Bent and P.V. Hentenryck, "A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows," Computers & Operations Research, vol.33, no. 4, pp. 875-893, 2003.
  11. I. M. Chao, "A tabu search method for the truck and trailer routing problem," Computers & Operations Research, vol. 29(1), pp. 33-51, 2002.
  12. J. G. Villegasa, C. Prinsb, C. Prodhonb, A. L. Medagliac and N. Velascod, "A matheuristic for the truck and trailer routing problem", European Journal of Operational Research, vol. 230, no. 2, pp. 231–244, 2013.
  13. S.-W. Lin, V. F. Yu and C.-C. Lu, "A simulated annealing heuristic for the truck and trailer routing problem with time windows," Expert Systems with Applications, vol. 38(12), pp. 15244-15252. 2011.
  14. K. Bruniecki, A. Chybicki, M. Moszyński and M. Bonecki, "Evaluation of vehicle routing problem algorithms for transport logistics using dedicated GIS system," presented at the 2016 Int. Scientific and Technical Conf. Geomatics of Baltic Geodetic Congress, Poland, Gdansk, Poland, to be published.
  15. U. Derigs, M. Pullmann and U. Vogel, "Truck and trailer routing Problems, heuristics and computational experience," Computers & Operations Research, vol. 40, no. 2, pp. 536-546, 2013.