CAPACITATED VEHICLE ROUTING PROBLEM WITH VEHICLES HIRE OR PURCHASE DECISION: MODELING AND SOLUTION APPROACHES

The overall cost of companies dealing with the distribution tasks is considerably affected by the way that distributing vehicles are procured. In this paper, a more practical version of capacitated vehicle routing problem (CVRP) in which the decision of purchase or hire of vehicles is simultaneously considered is investigated. In CVRP model capacitated vehicles start from a single depot simultaneously and deliver the demanded items of several costumers with known demands where each costumer must be met once. Since the optimal vehicle procurement cost is a function of total distance it traverses during the planning horizon, the model is modified in a way that the decision of purchasing or hiring of each vehicle is made simultaneously. The problem is formulated as a mixed integer programming (MIP) model in which the sum of net present value (NPV) of procurement and traveling costs is minimized. To solve the problem, a hybrid electromagnetism and parallel simulated annealing (PSA-EM) algorithm and a Shuffled Frog Leaping Algorithm (SFLA) are presented. Finally, the presented methods are compared experimentally. Although in some cases the SFLA algorithm yields better solutions, experimental results show the competitiveness of PSA-EM algorithm from the computational time and performance points of view.

Keywords:

capacitated vehicle routing problem , hire , purchase , parallel simulated annealing , electromagnetism-like algorithm , shuffled frog leaping.