Communications - Scientific Letters of the University of Zilina 2015, 17(2):11-14 | DOI: 10.26552/com.C.2015.2.11-14

Insertion Method for Multiple Messenger Problem with Multiple Depots

Jan Fabry1
1 Department of Econometrics, University of Economics Prague, Czech Republic

Messenger problem, as the variation of pickup and delivery problem, deals with the transport of a set of packages from their origins to given destinations. In reality, several vehicles have to be used to be able to satisfy all requirements within given time limit. Messengers can be located in one or multiple depots. Because of NP-hardness of the problem it is impossible, for most real problems, to find the optimal solution in acceptable time. Therefore, heuristic algorithms must be used. In the paper, insertion method for routes generation is presented. As the computational experiments in VBA for Excel show, obtained results can be improved using the exchange algorithm.

Keywords: multiple messenger problem; insertion method; exchange algorithm

Published: May 31, 2015  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Fabry, J. (2015). Insertion Method for Multiple Messenger Problem with Multiple Depots. Communications - Scientific Letters of the University of Zilina, 17(2), 11-14. doi: 10.26552/com.C.2015.2.11-14
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. CORDEAU, J.-F., LAPORTE, G., ROPKE, S.: Recent Models and Algorithms for One-to-One Pickup and Delivery Problems, pp. 327-357. In: GOLDEN, B. L., RAGHAVAN, S., WASIL, E. A. (eds.): The Vehicle Routing Problem: Latest Advances and New Challenges. Springer, 2008. Go to original source...
    2. CORDEAU, J.-F., LAPORTE, G. A.: The Dial-a-Ride Problem: Models and Algorithms. Annals of Operations Research, vol. 153, pp. 29-46, 2007. Go to original source...
    3. DE PAEPE, W. E., LENSTRA, J. K., SGALL, J., SITTERS, J. A., STOUGIE, L.: Computer-Aided Complexity Classification of Dial-a-Ride Problems, INFORMS J. on Computing, vol. 16, pp. 120-132, 2004. Go to original source...
    4. CORDEAU, J.-F.: A Branch-and-Cut Algorithm for the Dial-a-Ride Problem. Operations Research, vol. 54, pp. 573-586, 2006. Go to original source...
    5. TOTH, P., VIGO, D.: Heuristic Algorithms for the Handicapped Persons Transportation Problem. Transportation Science, vol. 31, pp. 60-71, 1997. Go to original source...
    6. JORGENSEN, R. M., LARSEN, J., BERGVINSDOTTIR, K. B.: Solving the Dial-a-Ride Problem Using Genetic Algorithms. J. of the Operational Research Society, vol. 58, pp. 1321-1331, 2007. Go to original source...
    7. FABRY, J., KOBZAREVA, M.: Multiple Messenger Problem. Proc. of Mathematical Methods in Economics '12, Karvina, pp. 141-147, 2012.
    8. FABRY, J.: Dynamic Messenger Problem. Communications - Scientific Letters of the University of Zilina, No. 4, pp. 66-69, 2007. Go to original source...
    9. PRIBYLOVA, L.: Heuristic Methods for Capacitated Messenger Problems (in Czech), Diploma thesis, University of Economics: Prague, 2014.
    10. CICKOVA, Z., REIFF, M., SURMANOVA, K.: Split Delivery Vehicle Routing Problem with Time Windows. Mathematical Methods in Economics 2014, Olomouc, pp. 128-132, 2014.

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content