Developing A Direct Search Algorithm for Solving The Capacitated Open Vehicle Routing Problem

Abstract

In open vehicle routing problems, the vehicle are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacited vehicle routing problem (CVRP). The strategy of releasing nonbasic variables from their bounds, combined with the “active constraint” method and the notion of superbasics, has been developed for efficienty requirments, this strategy is used to force the appropriate non-integer basic veriables to move to their neighbourhood integer points. A study of criteria fr choosing a nonbasic variable to work with in the inegerizing strategy has also been made. Succesful implementation of these algorithms was achieved on various test problem