IDEAS home Printed from
   My bibliography  Save this paper

The k-dissimilar vehicle routing problem


  • TALARICO, Luca
  • SÖRENSEN, Kenneth
  • SPRINGAEL, Johan


In this paper we define a new problem, the aim of which is to find a set of k dissimilar alternative solutions for a vehicle routing problem (VRP) on a single instance. This problem has several practical applications in the cash-in-transit sector and in the transportation of hazardous materials. A min-max mathematical formulation is developed that minimizes the objective function value of the worst solution. A distance measure is defined based on the edges shared between pairs of alternative solutions. An iterative heuristic algorithm to generate k dissimilar alternative solutions is also presented. The solution approach is tested using large and medium size benchmark instances for the capacitated vehicle routing problem.

Suggested Citation

  • TALARICO, Luca & SÖRENSEN, Kenneth & SPRINGAEL, Johan, 2013. "The k-dissimilar vehicle routing problem," Working Papers 2013029, University of Antwerp, Faculty of Applied Economics.
  • Handle: RePEc:ant:wpaper:2013029

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Azevedo, JoseAugusto & Santos Costa, Maria Emilia O. & Silvestre Madeira, Joaquim Joao E. R. & Vieira Martins, Ernesto Q., 1993. "An algorithm for the ranking of shortest paths," European Journal of Operational Research, Elsevier, vol. 69(1), pages 97-106, August.
    2. Dell'Olmo, Paolo & Gentili, Monica & Scozzari, Andrea, 2005. "On finding dissimilar Pareto-optimal paths," European Journal of Operational Research, Elsevier, vol. 162(1), pages 70-82, April.
    3. Jin Y. Yen, 1971. "Finding the K Shortest Loopless Paths in a Network," Management Science, INFORMS, vol. 17(11), pages 712-716, July.
    4. Helsgaun, Keld, 2000. "An effective implementation of the Lin-Kernighan traveling salesman heuristic," European Journal of Operational Research, Elsevier, vol. 126(1), pages 106-130, October.
    5. Akgun, Vedat & Erkut, Erhan & Batta, Rajan, 2000. "On finding dissimilar paths," European Journal of Operational Research, Elsevier, vol. 121(2), pages 232-246, March.
    6. van Leeuwen, P. H. & Volgenant, A., 1983. "Solving symmetric vehicle routing problems asymmetrically," European Journal of Operational Research, Elsevier, vol. 12(4), pages 388-393, April.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. TALARICO, Luca & SÖRENSEN, Kenneth & SPRINGAEL, Johan, 2014. "A bi-objective model to increase security and reduce travel costs in the cash-in-transit sector," Working Papers 2014026, University of Antwerp, Faculty of Applied Economics.

    More about this item


    Vehicle Routing Problem (VRP); Metaheuristic; Security; Similarity;

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ant:wpaper:2013029. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Joeri Nys). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.