جستجوی پیشرفته الگوریتم های مسیریابی برای مشکلات مدیریت عملیات پیچیده

Vehicle routing encompasses a whole class of complex optimization problems that target the derivation of minimum total cost routes for a number of resources (vehicles) located at a central point (depot) in order to service efficiently a number of demand points (customers). Several practical issues in the food industry, involving both production and transportation decisions are modelled as VRP instances and are hard combinatorial problems in the strong sense (NP-hard). For such problems, metaheuristics, i.e., general solution procedures that explore the solution space to identify high quality solutions and often embed some standard route construction and improvement algorithms have been proposed. This paper surveys the recent research efforts on metaheuristic solution methodologies for the standard and most widely studied version of the Vehicle Routing Problem (VRP), i.e., the Capacitated VRP. The computational performance of each metaheuristic is presented for the 14 benchmark instances of Christofides et al. [Christofides, N., Mingozzi, A., & Toth, P. (1979). Combinatorial optimization (p. 315). Chichester: Wiley].

The Vehicle Routing Problem (VRP) (Toth & Vigo, 2002) embraces a whole class of complex problems, in which a set of minimum total cost routes must be determined for a number of resources (i.e., a fleet of vehicles) located at one or several points (e.g., depots, warehouses), in order to service efficiently a number of demand or supply (or both) points (Angelelli and Speranza, 2002, Caricato et al., 2003, Ioannou et al., 2001, Ioannou et al., 2003, Tarantilis et al., 2004 and Tarantilis et al., 2002c). Although the VRP has been extensively used in the area of transportation science since 1960s, many managers have started employing VRP models during the last years for effective decision-making. The following are some examples of the multitude of VRP applications in manufacturing and service operations management. • Routing of automated guided vehicles, which are considered as one of the most appropriate modes for material handling in contemporary flexibly automated production environments (Herrmann et al., 1999 and Reveliotis, 2000). • Minimization of the distribution costs in a multi-facility production system (Dhaenens-Flipo, 2000). • Determination of vehicle routes for material delivery within the premises of a plant operating under a Just-In-Time philosophy (Vaidyanathan, 1999). • Sequencing of the operations in single or multi-feeder printed circuit board manufacturing (Altinkemer et al., 2000 and Kazaz and Altınkemer, 2003). • Scheduling wafer probing (Pearn, Chung, & Yang, 2002). • Rolling batch planning (Xiong, Weishui, & Xinhe, 1998). In this paper, we address the standard and most widely studied version of the VRP, i.e., the Capacitated VRP (CVRP). The CVRP is a combinatorial optimization problem defined on a graph G = (V, A), where V = {u0, u1, … , un} is the vertex set and A = {(ui, uj):ui, uj ∈ V, i ≠ j} is the arc set of G. Vertex u0 represents a depot (warehouse or distribution centre) that hosts a homogeneous fleet of m vehicles with capacity Q. The remaining vertices correspond to demand points (or equivalently, customers). Each customer ui has a non-negative demand qi. The vector of all customer demands is denoted by q(V). A service time si is required by each vehicle to unload the demand quantity qi at customer ui. Furthermore, a non-negative cost matrix C = (cij) is defined on A; usually, the cost cij models the travel time between customers i and j. If cij = cji, the problem is symmetric, and it is common to replace A with the edge set E = {(ui, uj):ui, uj ∈ V, i < j}. The cost of a route Rk = {u0, u1, … , um} is given by View the MathML sourcec(Rk)=∑i=0mci,i+1+∑i=1msi, where nodes u0 and um+1 coincide (they both represent the depot). The CVRP consists of designing a set of m routes such that (a) The total routing cost View the MathML sourcec(VRP)=∑i=1mc(Rk) is minimized. (b) Each route Rk starts and ends at the depot. (c) Each customer is visited exactly once by exactly one vehicle. (d) The total demand of any route does not exceed Q. The combinatorial nature of the CVRP is evident from the structure of the problem itself: a solution for the CVRP consists of a partition R1, … , Rm of V, and a corresponding permutation pk of Rk ∪ u0 specifying the order of the customers in the route k. It is important to note that the number of vehicles is either pre-determined or is treated as a decision variable. In other words, it may be assumed that m is greater than or equal to mmin, the minimum number of vehicles required to service all customers. The value of mmin can be computed by solving a bin packing problem (BPP) ( Gendreau, Laporte, & Semet, 2004) associated with the CVRP. The BPP can be stated as follows: Determine the minimum number of bins with equal capacity Q required for packing (loading) n items, each with a non-negative weight (demand) qi. Thus, a feasible solution for a given instance of the CVRP is also the result of an instance of the BPP. After determining mmin (the lower bound on the number of vehicles), the CVRP can be approached with m⩾mmin. Apart from the direct linkage between BPP and CVRP, the latter generalizes the well-known Travelling Salesman Problem (TSP) (Kabadi, 2002). The TSP arises when Q ⩾ q(V) and m = mmin = 1, allowing all the relaxations proposed for the TSP to be valid for the VRP. The major CVRP variable is a binary one associated with each arc in the graph, xij, that denotes if an arc is included in a route or not. Based on the variables xij, the following integer programming formulation can model the CVRP ( Ralphs, Kopman, Pulleyblank, & Trotter, 2003): Capacitated VRP

The complexity of the Capacitated Vehicle Routing Problem (CVRP) requires the employment of metaheuristic solution strategies for the majority of real-life applications. In this paper, we have surveyed the best known metaheuristic algorithms, according to their computational performance, in terms of solution quality, on the 14 benchmark instances generated by Christofides et al. (1979). The concept of adaptive memory as well as the granular-mechanism are probably the most power ideas put forward in the area of metaheuristics in recent years. In addition, the high quality solutions produced by BATA (Tarantilis et al., 2002a) and LBTA (Tarantilis et al., 2002b) encourages for future work on designing annealing-based metaheuristics with simple structure and few parameters for solving hard combinatorial optimization problems.