Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm
Authors:
- 31 October 2013
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 52 (9) , 2565-2575
Abstract
The vehicle routing problem (VRP) is a well-known combinatorial optimisation problem and holds a central place in logistics management. Many exact, heuristic and metaheuristic approaches have been proposed to solve VRP. An important variant of the VRP arises when a fleet of vehicles is fixed and characterised by different capacities for distribution activities. The problem is known as the heterogeneous fixed fleet VRP (HFFVRP). The HFFVRP is a natural generalisation of the VRP with several vehicle types, each type being defined by a capacity, a fixed cost and a cost per distance unit, and can cover more practical situations in transportation. This problem consists of determining a set of vehicle trips of minimum total length in which a set of customers is to be satisfied in the demand constraints using identical vehicles with limited capacity. If open routes instead of closed ones are considered in the HFFVRP, the problem becomes a heterogeneous fixed fleet Open VRP (HFFOVRP) which has numerous applications in industrial and service problems. In this paper, a bone route algorithm which uses the tabu search as an improved procedure is utilised to solve the HFFOVRP. The proposed algorithm was tested empirically on a 24 of generated VRPs, and compared with elite ant system and ant colony system. In all cases, the proposed algorithm finds the best-known solutions within a reasonable time.Keywords
This publication has 23 references indexed in Scilit:
- METAHEURISTIC APPROACH FOR THE MULTI-DEPOT VEHICLE ROUTING PROBLEMApplied Artificial Intelligence, 2012
- The open vehicle routing problem with fuzzy demandsExpert Systems with Applications, 2010
- Valid inequalities for the fleet size and mix vehicle routing problem with fixed costsNetworks, 2009
- APPROACHES FOR THE VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS DELIVERIES AND PICKUPSJournal of the Chinese Institute of Industrial Engineers, 2006
- Future paths for integer programming and links to artificial intelligenceComputers & Operations Research, 1986
- Routing with time windows by column generationNetworks, 1984
- A generalized assignment heuristic for vehicle routingNetworks, 1981
- A Heuristic Algorithm for the Vehicle-Dispatch ProblemOperations Research, 1974
- Scheduling of Vehicles from a Central Depot to a Number of Delivery PointsOperations Research, 1964
- The Truck Dispatching ProblemManagement Science, 1959