Metaheuristic Approaches for Vehicle Routing Problems

Metaheuristic Approaches for Vehicle Routing Problems

M. Saravanan (Department of Mechanical Engineering, RVS College of Engineering & Technology, Tamilnadu, India) and K.A.Sundararaman (Department of Mechanical Engineering, RVS College of Engineering & Technology, Tamilnadu, India)
DOI: 10.4018/jisscm.2013040102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Routing of service vehicles are the heart of many service operations. Exclusively vehicle routing problem (VRP) plays a central role in the optimization of distribution networks. The routing of service vehicles has a major impact on the quality of the service provided. In distribution of goods and services, it is time and again required to determine a combination of least cost vehicle routes through a set of geographically scattered customers, subject to side constraints. The case most commonly studied is where all vehicles are identical. Due to the complexity involved in solving the VRP, most researchers concentrate on using meta-heuristics for solving real-life problems. In this paper, heuristic methods based on Ant Colony Optimization and Simulated Annealing algorithms are developed and search strategies are investigated. Computational results are reported on randomly generated problems. These methods significantly improve in minimizing the total distances travelled by the vehicles.
Article Preview

Routing And Vehicle Routing Problems

Routing problems are often presented as graphical networks. The use of networks to describe these problems has the advantage of allowing the decision maker to visualize the problem under consideration. As an example, refer to Figure 1 (see Figure 1 in the Appendix). The Figure 1 (see Figure 1 in the Appendix) consists of five circles called nodes. Four of the nodes (node 2 through 5) represent pickup and/or delivery points, and a fifth (node 1) represents a depot node, from which the vehicle’s trip originates and ends. The depot node is the home base, from which the vehicle originates and ends.

Figure 1.

Routing network example

The depot node is the home base for the vehicle or product. Connecting these nodes are line segments referred to as arcs. Arcs describe the distance required to travel from one node to another. The numbers along the arcs in Figure 1 (see Figure 1 in the Appendix) are distances in kilometres. Directed arcs represent the direction of travel in routing problems. The small network in Figure 1 can be viewed as a route for a single vehicle. The route for the vehicle, also called a tour, is 1-2-3-4-5-1. The total distance for tour is 51 kilometres.

The tour described in Figure 1 (see Figure 1 in the Appendix) is a solution to a simple routing problem where the objective is to find the route that minimizes cost or any other criterion that may be appropriate. The minimum-cost solution, however, is subject to the tour being feasible. Feasibility depends on the type of problem, but, in general, implies that:

  • 1.

    A tour must include all nodes;

  • 2.

    A node must be visited only once;

  • 3.

    A tour must begin and at a depot.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2018): 1 Released, 3 Forthcoming
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