A Lexi-Search Approach of Variant Vehicle Routing Problem

Dr. Sobhan Babu K, Vijaya Kumar K, Purusotham S


The present study addresses a variant of vehicle routing problem (VRP). Let there are n- nodes, among them a class of ni (<<n) nodes may act as source nodes for loading/reloading the goods and the rest of the nodes may require the goods which available at the source nodes. The requirement for the nodes is supplied through a vehicle, it has a finite capacity. The aim is to find an optimal trip schedule for the capacitated VRP which minimizes the total distance such that the vehicle has to traverse through a node exactly once according to the precedence relation and meet the requirements at the nodes. Here the precedence relation says that i<j, which means, before reaching the jth node, an ith node must covered in the trip schedule and it is not necessary that the jth node is an immediate successor. The problem often can be modeled as a zero-one programming problem. The problem is having a variety of applications in logistics, networking theory, routing and allied areas. To solve the proposed problem we planned to develop an exact algorithm called Lexi-Search Algorithm. For implementation of the algorithm we would like to develop a suitable code using C-Language.

Keywords: Vehicle Routing Problem, Precedence Relation, Lexi-Search Algorithm, Zero-One Programming. Hamiltonian Cycle, Re-loading nodes.

Full Text:


DOI: https://doi.org/10.26483/ijarcs.v6i1.2407


  • There are currently no refbacks.

Copyright (c) 2016 International Journal of Advanced Research in Computer Science