An Improved Genetic Algorithm for Solving Multi Depot Vehicle Routing Problems

An Improved Genetic Algorithm for Solving Multi Depot Vehicle Routing Problems

Varimna Singh (Som Lalit Institute of Management Studies, Ahmedabad, India), L. Ganapathy (National Institute of Industrial Engineering, Mumbai, India) and Ashok K. Pundir (National Institute of Industrial Engineering, Mumbai, India)
DOI: 10.4018/IJISSCM.2019100101

Abstract

The classical Vehicle Routing Problem (VRP) tries to minimise the cost of dispatching goods from depots to customers using vehicles with limited carrying capacity. As a generalisation of the TSP, the problem is known to be NP-hard and several authors have proposed heuristics and meta-heuristics for obtaining good solutions. The authors present genetic algorithm-based approaches for solving the problem and compare the results with available results from other papers, in particular, the hybrid clustering based genetic algorithm. The authors find that the proposed methods give encouraging results on all these instances. The approach can be extended to solve multi depot VRPs with heterogeneous fleet of vehicles.
Article Preview
Top

2. Literature Review

Earlier research on multi-depot VRP can be seen in the decade of 1970’s from the works of Cassidy and Bennet (1972), Wren and Holliday (1972), and Gillett and Johnson (1976). The works of Laporte et al. (1984), Kulkarni and Bhave (1985), Laporte et al. (1988), Renaud et al. (1996), Cordeauet al. (1997) and Salhi and Sari (1997) can be considered as pioneering in MDVRP. Due to the complexity of the problem, MDVRP has continued to attract the interest of researchers (Skok et al., 2000a; Dondo et al., 2003; Tarantilis et al., 2004; Nagy and Salhi, 2005; Ho et al., 2008; Kek et al., 2008; Liu and Shen, 1999; Contardo and Martinelli, 2014; Rahimi-Vahed et al., 2015). Several heuristics for solving the problem can be found in the literature (Crevier et al., 2007; Ramalingam and Vivekanandan, 2014; Salhi et al., 2014). Among the recent works, Malairajan et al. (2013) proposed a decision support system for real-time VRP with backhaul for the Indian dairy industry. Saravanan and Sundararaman (2013) developed heuristics methods based on Ant Colony Optimization and Simulated Annealing algorithm to solve the VRP. Golias et al. (2013) deal with the scheduling of inbound and outbound trucks to the available inbound and outbound doors at a cross-dock facility. A memetic algorithm has been developed to solve the resulting problem with reasonable computational effort. Table 1 provides a summary list of select publications in this area along with the heuristic approach used to solve the MDVRP.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 13: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 12: 4 Issues (2019)
Volume 11: 4 Issues (2018)
Volume 10: 4 Issues (2017)
Volume 9: 4 Issues (2016)
Volume 8: 4 Issues (2015)
Volume 7: 4 Issues (2014)
Volume 6: 4 Issues (2013)
Volume 5: 4 Issues (2012)
Volume 4: 4 Issues (2011)
Volume 3: 4 Issues (2010)
Volume 2: 4 Issues (2009)
Volume 1: 4 Issues (2008)
View Complete Journal Contents Listing