A Hybrid Genetic Algorithm-Simulated Annealing Approach for the Multi-Objective Vehicle Routing Problem with Time Windows

Introduction

Vehicle routing problems (VRP) are concerned with the delivery of some commodities from one or more depots to a number of customer locations with known demand. Such problems arise in many physical systems dealing with distribution, for example, delivery of commodities such as mail, food, newspapers, etc. The specific problem which arises is dependent upon the type of constraints and management objectives. The constraints of the problem may arise from particular factors such as the vehicle capacity, distance/time restriction, number of customers to be serviced by a vehicle, and other practical requirements. The management objectives usually relate to the minimization of cost/distance or fleet size (Achuthan et al., 1997). Among variants of VRP, the VRP with capacity and time window constraints is called vehicle routing problem with time windows (VRPTW) (Hashimoto et al., 2006). VRPTW is a non polynomial-hard (NP-hard) problem, which is encountered very frequently in making decisions about the distribution of goods and services. The problem involves a fleet of vehicles set off from a depot to serve a number of customers, at different geographic locations, with various demands and within specific time windows before returning to the depot. The objective of the problem is to find routes for the vehicles to serve all the customers at a minimal cost (in terms of travel, distance, etc.) without violating the capacity and travel time constraints of the vehicles and the time window constraints set by the customers (Tan et al., 2001). Although cost minimization function is the mostly used function in the VRPTW literature, there may be a need to consider more than one objective in some cases. When the related literature is investigated, Garcia-Najera and Bullinaria (2009), Tang et al. (2009), Müller (2010), Jeon et al. (2007) are some of the papers in which multiple objectives are considered for VRPTW. For a comprehensive literature review for multi-objective VRPTW concept, Jozefowiez et al. (2008) can be reviewed.

The methodologies for solving VRPTW can be classified as given below. This classification is referenced from Badeu et al. (1997) and the literature review is updated:

• •

  Exact algorithms (Az, et al., 2007; Kallehauge, 2008; Desrochers et al., 1992),

• •

  Route construction heuristics (Thangiah et al., 1996; Potvin and Robillard, 1995; Russell, 1995; Potvin and Rousseau, 1995; Solomon, 1987),

• •

  Route improvement heuristics (Dror and Levy, 1986; Solomon et al., 1998),

• •

  Composite heuristics that include both route construction and route improvement procedures (Chen et al., 2006; Du et al., 2005; Du et al., 2007; Kontroravdis and Bard, 1995),

• •

  Metaheuristics (Scatter Search (Russell and Chiang, 2006); Tabu Search (Ho and Haugland 2004; Rochat and Taillard, 1995; Taillard et al., 1995; Potvin and Rousseau, 1995); Simulated Annealing (Tavakkoli et al., 2006; Breedam, 1995); Ant Colony (Cheng and Mao, 2007; Mazzeo and Loiseau, 2004; Bell and McMullen, 2004); Genetic Algorithms (Osman et al., 2005; Prins, 2004; Baker and Ayechew, 2003; Hwang, 2002)).