Article Preview
Top1. Introduction
In today’s competitive environment, an optimized route plan of vehicles can maximize the profit earned and customer satisfaction level for a company. In addition to this, it may result in less emission of CO2 in the environment. As a result, huge research efforts have been devoted for optimized route plan of vehicles. Vehicle Routing Problem (VRP) is one of the popular research area that finds least cost routes for homogenous vehicles that serve a number of geographically scattered customers with fixed demands. The classical VRP was first formulated by Dantzig et. al (1959), attention has been devoted to more realistic variants of VRP (Sandhya, V. K. (2013), Goel R. et. al. (2109)). The survey on classical VRP, its variants, solution methods and issues is available in Rajeev and Raman Maini (2017).
In realistic distribution problems, customer demands are fulfilled by heterogeneous fleets of vehicles. The aspect of fleet dimensioning, composition and allocation is common issue in most of the industries. These factors are highly dependent on various market factors like vehicle holding, vehicle depreciation, resale, leasing prices, vehicle capacity, transport cost, transport demand, weight and size limitation on roads and narrow streets at urban areas etc. In addition, to this a fleet with vehicles of different capacities is cost effective towards demand variations.
The variant of the VRP in which one must also considers on the fleet composition is known as the Heterogeneous Fixed Fleet Vehicle Routing Problem (HFVRP). The very first work in this area was formulated by Golden et. al (1984). The HFVRP is dissimilar from the classical VRP in that it deals with a heterogeneous fleet of vehicles having varied capacities, fixed and variable costs. As a result, HFVRP consists of determining simultaneously the composition and design of the optimized routes for a set of heterogeneous fleets of vehicles, each starting and ending at central distribution center, that fulfills the known demand of ‘n’ customers, such that constraints of classical VRP are preserved. The constraints that are taken into account in classical VRP are: (i) all vehicle routes start from and finish at depot (ii) every customer is visited exactly once (iii) summation of demand of all the customers served on each route must not exceed the total capacity of the vehicle. (iv) total number of vehicles used to construct complete route must not exceed the total number of available vehicles and (v) each customer be completely served by a single vehicle. In literature, there are two major categories of heterogeneous vehicle routing problem: (a) if the number of vehicles is fixed then the problem is called heterogeneous fixed fleet vehicle routing problem (HFFVRP) (b) if there are unlimited number of available vehicles then the problem is known as fleet size and mix vehicle routing problem (FSMVRP). Beside these two major categories mentioned here, other versions of these two such as HFVRP with time windows, HFVRP with multi trips, HFVRP with split deliveries also exist. Detailed information regarding these variants is available in Koç, Çağrı, et al (2016).
The HFVRP which we propose to solve in this study is NP-Hard problem, as it reduces to classical VRP when all vehicles are identical. Some methods that try to obtain their exact solution have been proposed in literature since its introduction by Golden et al. (1984) .Yaman (2006) proposed valid inequalities and developed lower bounds for the FSMVRP. Choi and Tcha (2007) developed lower bounds for all FSM variants using a column generation algorithm based on a set covering formulation. Baldacci et al. (2008) developed two valid inequalities based on two-commodity MIP formulation for the FSMVRP. Later, Pessoa et al. (2009) developed a robust Branch-Cut-and-Price algorithm for solving instances up to 75 customers optimally. Baldacci and Mingozzi (2009) put forward a unified exact algorithm based on SP approach. Bounding procedures used in this study are based on linear relaxation and Lagrangian relaxation. The developed algorithm obtained even better results and could solve a few instances with 100 customers. However, HFVRP is NP-Hard, and therefore, exact methods are not possible for solving large instances. Generally, meta heuristics are chosen over exact methods for solving large size problems. This has motivated researchers to develop several heuristics/meta heuristics for solving HFVRP.