Article Preview
TopIntroduction
In today’s competitive world, distribution of goods is one of the important processes and it is the central focus point in the supply chain and logistics fields. Numerous companies are known for significant drops of their running costs due to the efficient coping with distribution networks. Therefore, several studies and research works are continuing to model and solve transportation problems, especially vehicle routing problems (VRPs) which are an extension of travelling salesman problem (TSP) (Martinovis & Bajer, 2012). There are several papers on TSP. Recently, Dong et al. (2016) have developed a new method to solve a special type of TSP problem. The challenge in Vehicle Routing Problem is to determine some set of paths for all the vehicles used to serve the customers. The open type of VRP is called open vehicle routing problem (OVRP) in which vehicles are not return back to the central hub called depot after visiting all the customers. Several publications applying different types of heuristic and metaheuristic methods for this problem have already been released. Brandao (2004) and Fu et al. (2005) used tabu search (TS) in the Open Vehicle Routing Problem having some limitations on capacity of vehicles and distance travelled. Tarantilis et al. (2005) used the list-based threshold accepting method to solve the Open Vehicle Routing Problem (OVRP) and this method also proposed how to solve the OVRP with more than one depots (Tarantilis & Kiranoudis, 2002). Pisinger and Ropke (2007) also proposed a heuristic based on neighborhoods search in this type of problem. Li et al. (2007) presented a travelling heuristic and a deterministic type of simulated annealing method in this problem. Fleszar et al. (2009) also designed a search method based on variable neighborhoods for the OVRP. Cao & Lai (2010) had designed OVRP with fuzzy demands. Zachariadis and Kiranoudis (2010) presented new a metaheuristic which is basically one type of local search technique. Li et al. (2012) used a variety of tabu search algorithm with metaheuristic of multi start adaptive memory programming in OVRP with heterogeneous type of vehicles, in which the capacity and costs per unit distance of vehicles are heterogeneous. Recently Marinakis and Marinaki, (2011) proposed a new algorithm for OVRP by mimicking the mating procedure of bee.
The original form of VRP uses one central point called depot and all the vehicles has to start from that and return back to it after giving the services to their customers. Every customer will be in different locations and they will have some demands. Every vehicle has to visit and give service to a set of customers assigned to that vehicle and there is a constraint in the capacity of those vehicles (Chiang & Hsu, 2014). OVRP was first introduced by Sariklis and Powell (2000). It is encountered in many real situations, for example, the organizations that hire vehicles from other transport organizations and in this case, those vehicles need not require returning to the depot after the completion of service (Cao & Lai, 2010) (Lin et al., 2014). But the situations where the vehicles have to return back, they follow the same route in which they came and then the visiting of customers will be just the opposite order. This fact implies that the OVRP is a case of searching the Hamiltonian path for all the vehicles whereas the basic form of VRP is a case of searching the Hamiltonian cycle for all the vehicles. So OVRP can be designed as a problem of finding the least distance Hamiltonian path for all the vehicles used where there will be only one central depot from where the vehicles start (Aksen, Özyurt, & Aras, 2007). This problem is NP hard as any type of the Hamiltonian path problem is just a modified version of the TSP problem that is basically a NP hard problem (Reinelt, 1994). So like TSP, the Open Vehicle Routing Problem is also not an easy problem to solve. In terms of the motive of the OVRP, all the researchers make an assumption that the price of hiring an extra vehicle increases the transportation cost due to this extra route (Fu, Eglese, & Li, 2005). At the duration of 1980 and 1990, very little work has been published on OVRP in the field of operation research and computer science. But after that period and still now many researchers are working in this area and several variety of VRP is developed.