Meta heuristic approaches for solving variants of vehicle routing problem with mid way halts

Abstract

Logistics plays a vital role for any distribution management. The distribution of goods from production centres or central depot to customers are addressed under the topic Vehicle Routing Problem (VRP) in the literature. VRP is an important area of research in Operations Research Community. It is a NP-hard Combinatorial Optimization Problem. The objective of VRP is to design low cost route with a set of homogenous vehicles available at the depot to serve a set of geographically distributed customers. The route begins and ends with the central distribution centre serving each customer once and returning to the depot. To solve VRP, many algorithms including heuristics are designed. As VRP provides real life solution for several problems, many researchers have contributed different solution methodology for solving the problem. Different variants on VRP like Stochastic VRP (SVRP), VRP with Time Windows (VRPTW), Multi Depot VRP (MDVRP), VRP with Pickup and Delivery (VRPPD) etc. are developed using additional constraints. In addition to these traditional variants, new objectives and constraints that address the real time issues are incorporated into VRP. These include pollution routing problem, hazardous materials transportation and routing, perishable goods routing, environment friendly routing, emergency routing to name a few. The focal point of this research work is to study a variant of VRP namely Vehicle Routing Problem with Mid way Halts (VRPMH). The objective of VRPMH is to devise low cost route for a set of geographically distributed customers by a fleet of homogenous vehicles stationed at a depot where the vehicle halts in between for some service in facility centres/service centres. This study proposes to introduce frameworks on VRPMH by incorporating real life objectives and constraints and also proposes to devise environment friendly routing for vehicles. The frameworks designed for VRPMH can be modelled for any facility centre like ware houses, fuel stations, toll booths etc., along with the problem specific constraints. To carry out the research further with experiments and to validate the framework, the entire research work is discussed with the facility centre as refuelling station. The motivation behind the selection is due to Green Vehicle Routing Problem (G-VRP). The objective of G-VRP is to design low cost route to serve a set of geographically distributed customers which include halts at alternate refuelling stations. When vehicles are engaged to serve customers, apart from halting at customer location they halt for some service in the facility centres which has an impact on the overall cost of the route. Minimizing the number of halts can minimize the route cost. In line with this, the framework Vehicle Routing Problem with Limited Midway Halts (VRPLMH) is modelled which aim to minimize both route cost and number of halts at facility centres and is modelled using constraint optimization. This framework is extended to propose a model Green VRP with Limited refuelling Halts (GVRP-LHS). The problem is solved using Particle Swarm Optimization with a devised mutation operator called Greedy Mutation Operator (PSO-GMO). When the facility centres are limited, vehicle spend considerable amount of time in these centres to get some service which force vehicles to wait in a queue. To facilitate this, facility centres are modelled with an M/M/1 queue model. The routing decision is influenced by the time spent by the vehicle in the system which includes the waiting time and the service time. To address these issues Vehicle Routing Problem with Queue equipped Mid way Halts (VRPMHQ) is introduced which is extended for G-VRP as Green VRP with Queues (G-VRPQ). The problem is solved using an enhanced Chemical Reaction Optimization (e-CRO). Generally, catalysts are used to speed up the chemical reaction, similarly, to enhance the capability of chemical reaction optimization, bacterial transformation is used that acts as a catalyst to enhance the reaction. The results predict the impact of wait time on the overall route cost. In recent times, green logistics is gaining popularity. Green logistics is vehicle routing with environmental concerns. As transportation sector is a major contributor of Green House Gas (GHG) emissions, considerable efforts are made to have an environment friendly routing. The objective of green logistics is to study the impact of vehicle routing on the environment and the possible reduction of GHG emission in particular carbon-di-oxide. This work reports and measures the emissions that arise with VRPMH. Generally, the amount of emission is measured for vehicle in cruise. But, emission also arises in idling vehicles and left unaddressed. As VRPMH has halts at facility centres apart from serving the customers, idling emission is realized which has a considerable impact on the total emission estimation. This work estimates emission from vehicles for G-VRP using Methodology for estimating Transport Emission and Energy consumption (MEET) for vehicles in cruise. As idling emission estimate is hard to compute an approximate estimate for vehicles in both cruise and idling state is determined using air/fuel mixture ratio. The results project the impact of idling emission on the total emission. To further explore the impact of emission on environment, fuel consumption, a factor that is influential in emission is studied as there is a positive correlation between fuel consumption and emission. A framework called a Fuel efficient VRPMH (F-VRPMH) is proposed and is extended to G-VRP as a Fuel efficient Green Vehicle Routing Problem (F-GVRP) with varying speed constraint which is simulated using triangular distribution. It is modelled as a bi objective optimization problem that aims to minimize both route cost and fuel consumption using goal programming. The problem is solved using PSO with Greedy Mutation Operator equipped with time varying acceleration (TVa-PSOGMO). Experiments are conducted with different speed intervals on G-VRP data set and the impact of constant and varying speed on fuel consumption is analyzed. There are a class of vehicles which are not part of any distribution logistics or public transport system but are part of road transport and emission. One such vehicle chosen for a case study is Mobile Advertisement Vehicle Routing Problem (MAVRP). The task of these vehicles is to move around the city along a specified route and gather the attention of people to advertise the products with halts at refuelling stations. The problem is modelled with hierarchical objectives with time dependent speed parameter and is solved in two phases. In the first phase a minimum cost route is obtained using hybrid PSO which is then improved for a minimum emission route using local exchange operator based on speed and congestion