Keywords

1 Introduction

Vehicle routing problems (VRPs) are combinatorial optimization problems that appear in relevant practical applications covering many different domains from the distribution of goods to the delivery of services. The goal is to build one or several vehicle routes in order to service a set of customers. This family of combinatorial optimization problems has attracted widespread research in the past decades. Indeed, it arrives at the top list of the more studied fields in operations research (Laporte 2009).

Routing problems are usually solved through a single objective aiming to minimize a cost, whereas improvements on the solution cost often have a direct impact on other important factors. Indeed, in real-world applications, one can be interested by optimizing simultaneously other criteria such as fleet size, work balancing, or customer satisfaction.

The aim of this survey is to provide an overview on routing problems for which more than one objective function must be optimized. Boffey (1995) made a first classification of these topics and presented several useful solution methods. Later, Jozefowiez et al. (2008b) proposed an updated review based on objectives, then on problems, and finally on methods. Our contribution is to refer mainly to papers dealing with vehicle routing which have been published over the last half decade (i.e., those appeared since the last survey from Jozefowiez et al. (2008b)) and to classify them according to the kind of problem. A short review on other multi-criteria problems encountered in the logistic field and involving routing decisions such as shortest path computation or distribution network design is also presented.

This chapter is organized as follows: the classical vehicle routing problem and an overview on multi-objective combinatorial optimization are introduced in the Sect. 1.2. Section 1.3 provides an overview on multi-criteria studies involving the basic vehicle routing problem as a central part. In Sect. 1.4, the principal studies dealing with complex constraints and/or unusual criteria are given. Section 1.5 is dedicated to recent trends on routing problems involving path, flow, or network design in a multi-criteria environment. Section 1.6 provides a classification of the published literature on the subject. A conclusion and some future directions for research are drawn in Sect. 1.7.

2 Background

Before presenting the papers related to the review proposed here, it might be necessary to give some settings of the problems under consideration. Thus, this section first recalls the capacitated vehicle routing problem (CVRP) and introduces some notions on multi-objective optimization.

2.1 Basic Vehicle Routing Problem

Capacitated Vehicle Routing Problem involves the routing of vehicles with common limited capacity from a central depot to a set of customers at minimal cost. It can be modeled by a complete graph G = (X, A) where X = {0,1,…,n} is a set of vertices, and A = {(i, j) | ∀i, j ∈X, i ≠ j} is a set of arcs. Vertex 0 corresponds to the depot where is based a homogeneous fleet of vehicles with a limited capacity W. The remaining n vertices are the customers. Each customer i has a known demand q i . Each arc (i, j) is associated to a value d i,j which represents the cost of the shortest path linking the nodes i and j. This value can be a monetary cost, a distance, a time, etc. The aim is to build a set of routes with a minimal total cost servicing each customer exactly once, without exceeding the vehicle capacity. The CVRP has been proved NP-hard (Lenstra and Rinnooy Kan 1981), for an overview on mathematical formulations, exact and approximate methods designed to solve this problem; see for example, Toth and Vigo (2002) and Laporte (2009).

Some other surveys dealing with more complex variants of the vehicle routing problems have appeared recently in the literature. Hoff et al. (2010) provide an overview dedicated to routing and fleet composition problems, where the fleet is composed of several types of vehicles associated with different fixed and variable costs. This last paper focuses on aspects related to industrial applications. Labadie and Prins (2012) present also a survey summarizing the most important results on the majority of vehicle routing variants, with an emphasis on problems occurring in developing countries. In Baldacci et al. (2012), mathematical formulations, relaxations, and recent exact methods developed to resolve the CVRP and the VRP with time windows (VRPTW) are given. VRPTW is the most widely studied variant of the CVRP and differs from this last on the fact that for each customer is associated a time slot within which its service must start. Classification schemes as well as exact and heuristic algorithms are given in Nagy and Salhi (2007) for the location-routing problem. In this relatively recent category of problems, simultaneously to routing decisions one looks on how to locate optimally the depots from which the customers would be serviced. Capacitated arc routing problem (CARP) is the arc counterpart of the CVRP in the sense that focus regarding service and resource constraints are on the links and not on the nodes of the given graph. This routing problem is much less studied in the literature inspite of its numerous applications such as electrical lines inspection, snow removal, garbage collection, etc. For an extended survey on this problem, its variants, formulations, and resolution approaches see the paper by Wøhlk (2008).

Contrarily to the problems cited above, in routing problems with profits it is not necessary to service all the customers. In this branch of problems, each customer (node) is associated to a positive score or profit which is collected only if the corresponding node is visited. Interested readers are referred to Feillet et al. (2005) and to Vansteenwegen et al. (2011) for a survey on the different categories of problems and the corresponding results appeared in the literature.

In covering tour problems, some locations must just be covered and not necessarily visited. Such kind of problems have many applications in delivery services such as health care to rural population in developing countries. The aim is to build a tour visiting some centers with a minimal total length in order to guarantee coverage of a set of customers (population). This notion of coverage is often associated to a given distance, which is considered as a problem parameter. These problems are by nature multi-criteria since at least they can aim to minimize the tour length or cost, maximize the population covered, and minimize the maximal distance to a center included in the tour.

Most published papers on problems involving routing problems concern the single objective case. Multi-objective studies attract very less attention, although in real-word applications several objective functions are often expressed. This chapter targets to gather recent studies published since the last survey by Jozefowiez et al. (2008b) on the most important vehicle routing problems generalizing the basic CVRP and CARP, and especially the problems cited above. Recent developments on some other problems involving routing decisions are also mentioned in this survey.

2.2 Multi-objective Optimization

In single objective optimization, the goal is to find one solution (or in special cases multiple optimal solutions but with the same objective function value). In multi-objective optimization, this is not sufficient since problems deal with more than one objective function constituting a multi-dimensional objective space. The aim is then to find the set of so-called Pareto-optimal solutions or efficient solutions. A feasible solution x 1 is called efficient if there does not exist another feasible solution x 2 such that the value of x 2 is better or equal to the value of x 1 for all objective functions, with a strict inequality for at least one of the objectives. Otherwise, x 2 dominates x 1 .

The main goal in multi-objective optimization is to find a set of solutions that approximates well the Pareto-optimal set (or the non-dominated vectors in the objective space), i.e., (1) as close as possible to the Pareto-optimal front and (2) as diverse as possible to guarantee a good set of trade-off solutions.

A first approach is to transform and solve a single objective problem through a weighted metric method that scalarizes the set of objectives. The resulting solutions are defined as the set of supported efficient ones, SE. However, a routing problem is usually combinatorial leading to a multi-objective combinatorial optimization (MOCO). The fact to deal with discrete variables has a strong consequence on the difficulty of such problems. Although the objectives are usually linear functions, there may exist efficient solutions, called non-supported efficient solutions NE which are not optimal for any weighted sum of the objectives. Finding the non-supported solutions contributes essentially to the difficulty of MOCO problems. Thus, a two-phase method can be applied. In the first phase, SE is found using the scalarization technique, and solving single objective problems. The second phase consists of finding the non-supported efficient solutions by problem-specific methods using bounds, reduced costs, etc.

Another approach is the adaptation of metaheuristic techniques. A first kind consists of defining search directions by a local aggregation of the objectives, often based on a weighted sum. Thus, starting from an initial solution and a given direction, an approximation of a part of the Pareto-optimal front can be found. The principle is repeated on several directions to retrieve completely the non-dominated frontier. A second kind is based on both a population of solutions and the notion of dominance to approximate the non-dominated frontier. It has the advantage of searching for many efficient solutions per iteration. Finally, there exist also specific procedures and hybrid methods.

For more details and guidelines on the development and use of the most effective metaheuristics methodologies for MOCO see, for example, Deb et al. (2000), Deb (2002), Angus and Woodward (2009). The two first papers are dedicated to multi-criteria evolutionary algorithms and the last one deals with ant colony systems. In Martí et al. (2011), a methodology for adapting the hybrid metaheuristic greedy randomized adaptive search procedure (GRASP) combined with the path relinking approach (PR) is developed for multi-criteria problems. The most frequently used resolution approaches are based on multi-criteria evolutionary algorithms which are detailed through numerous surveys such as the papers by Coello Coello et al. (2005), Coello Coello (2009), Zhou et al. (2011).

3 Multi-criteria Analysis for the Basic Routing Problem

This section aims to make a census of multi-criteria studies involving the basic routing problem, i.e., problems without extra constraints or attribute. The studies cited here consider the CVRP defined above as a core problem but add one or more criteria which must be optimized simultaneously in addition to a cost function.

The study by Parc and Koelling (1986) is the pioneer one dealing with multi-objective CVRP. In this work, the classical CVRP is considered with three conflicting criteria: minimization of the total distance traveled; minimization of the total deterioration of goods during transportation; and maximization of fulfillment of emergent services and conditional dependencies of customers. This third criterion is relevant for cases where some customers should be serviced urgently or are contingent upon others. Two customers are said to be contingent when there is a conditional dependency between them; these dependencies could be resulting from operational, functional, or economic reasons. The problem is resolved using heuristics that take into account the decision makers’ preferences.

Since then, many papers have been devoted to this issue. From the recent years, we can quote Jozefowiez et al. (2009) who consider a CVRP in which the total route length and the route imbalance are minimized concurrently. The second criterion in this study consists in minimizing the difference between the longest route and the shortest one. A multi-objective evolutionary algorithm using a new mechanism, called the elitist diversification, is used in cooperation with a sharing method and parallelization techniques to resolve the problem. In a previous study, these authors (Jozefowiez et al. 2005) considered the same problem and resolved it with an enhancement of the popular NSGA-II (Non-dominated Sorting Genetic Algorithm).

The study by Chand et al. (2010) deals with a bi-criteria CVRP in which the number of vehicles and the total cost (distance) are minimized. A genetic algorithm-based approach is designed to resolve this problem; however, in this study the authors do not look for a Pareto front but for a single solution. This one has to be optimized for each objective so that, if we try to optimize it any further, the other objective(s) will suffer as a result. The approach is tested using problem instances reported in the literature, derived from publicly available Solomon’s benchmark data for VRP. According to the authors, the results show that the GA approach is able to find high quality solutions but unfortunately they do not provide comparisons with previous studies.

For the arc counterpart of the CVRP, namely the capacitated arc routing problem (CARP), we are only aware of one study due to Lacomme et al. (2006). In this work, in addition to the frequently used criterion which is the total cost of the trips, a second criterion related to the makespan, as in scheduling problems, is minimized conjointly. This second objective function consists in minimizing the longest trip and the bi-criteria CARP is solved thanks to an efficient non-dominated sorting genetic algorithm (NSGA-II).

4 Multi-criteria Analysis for VRP with Rich Structure

4.1 Vehicle Routing with Time Windows

Vehicle Routing Problem with Time Windows extends the basic CVRP by adding time constraints on customers’ service. In this variant, to each customer i is associated a predefined time lag [b i , e i ], within the service must start. A time window [b 0 , e 0 ] is often considered for the depot’s opening hours, and traveling times t ij are defined in addition to distances d i,j . Due to its academic interest and its numerous real-life applications (such as in maintenance routing problems), VRPTW is drawing more and more attention in the research community. Most of the published literature deals with hard time windows. In this case, when a vehicle arrives at customer i before b i , it has to wait and it is not allowed to service a customer after the closing time e i . In some versions, late and/or early services are permitted but penalty costs must be paid (soft time windows). Contrary to the CVRP, deciding whether m routes are enough to visit all customers is an NP-complete problem. Most authors minimize the number of vehicles required and then the total distance performed; traveling times are just used to check time windows. The VRPTW is NP-Hard and instances with 100 customers or more are very hard to solve optimally. The majority of resolution methods are approximations, and evolutionary algorithms account for the greater part.

When the number of vehicles is to be minimized in priority, the best metaheuristics are the memetic algorithm of Nagata et al. (2010) and the arc-guided evolutionary algorithm of Repoussis et al. (2009). Labadie et al. (2008) design an effective memetic algorithm for total distance minimization, as in the CVRP. The same algorithm is also able to resolve efficiently the problem where the number of vehicles must be minimized in priority before the total distance. For a complete overview on resolution approaches for the VRPTW, one can see the surveys of Bräysy and Gendreau (2005a, b).

The multi-criteria version of the VRPTW is without any doubt, the most investigated among multi-objective vehicle routing problems. Rahoual et al. (2001) design an NSGA-based genetic algorithm for the VRPTW for minimizing the number of routes, the travel distance, and the penalties associated with violated constraints.

Tan et al. (2006) and Ombuki et al. (2006) consider the VRPTW as a bi-objective optimization problem, minimizing the number of vehicles and the total travel distance. Both studies propose a genetic algorithm for solving the problem and use the standard Solomon’s benchmark to assess the quality of the developed approaches (see Solomon (1987) for more details). In the former study, a Pareto ranking techniques is used to assign fitness to individuals, design a new crossover operator called route-exchange crossover, and use a multi-mode mutation which considered swapping, splitting, and merging of routes. The latter propose the genetic operators best cost route crossover and constrained route reversal mutation, which is an adaptation of the widely used inversion method.

In Ghoseiri and Ghannadpour (2010), the same problem as in Tan et al. (2006) and Ombuki et al. (2006), is studied. The authors propose a goal programming approach and a genetic algorithm in which the decision maker specifies optimistic aspiration levels to the objectives and deviations from those aspirations are minimized. The method is applied to solve Solomon’s benchmark of 56 VRPTW instances with 100 customers. The results are compared to the best known solutions obtained for the single objective case or to the two previous studies cited above and are proved to be competitive.

In the study of Wang and Li (2011), a multi-objective VRP considering time window constraints is also investigated. The authors consider two objective functions, the first consists in minimizing the total distance while the second maximizes client satisfaction by fulfilling time-window requirements. A hybrid genetic algorithm was designed to solve the problem; the numerical evaluations of this method are driven on a military application.

Garcia-Najera and Bullinaria (2011) study the VRPTW with three criteria to minimize: the total crossed distance, the overall traveling time, and the fleet size. This paper proposes a multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the problem. The numerical results obtained on Solomon’s instances show that when the similarity measure is used, the diversity and the quality of solutions are improved. Furthermore, the algorithm achieves competitive results since it provides better Pareto front approximations.

In Muller (2010), a VRP with soft time windows (VRPSTW) is considered. That means violations of the time windows are allowed, but associated with penalties. The problem studied resides in determining optimally the routes so as to minimize simultaneously the total costs, consisting of the number of used vehicles and the total distance, on one part and the penalties on the other part. The problem is formulated as a bi-criteria minimization problem and heuristic methods are used to calculate approximations of the Pareto optimal solutions. Experimental results show that in certain cases the allowance of penalties leads to significant savings of the total costs.

Tavakkoli-Moghaddam et al. (2005) consider the VRPSTW with a heterogeneous fleet of vehicles. Three criteria are to minimize: fleet cost, routes cost, and violation of soft time windows penalty. The authors use a simulated annealing (SA) approach with the classical 1-Opt and 2-Opt operators for solving the problem. More recently, Tavakkoli-Moghaddam et al. (2011) have considered again a new variant of the VRPTW with two objective functions to optimize. The authors call this problem a VRP with competitive time windows (VRPCTW) and the considered criteria are the total traveling time to minimize and the total amount of sales to maximize. In this new problem that occurs in a competitive environment, the demand of each customer is constituted of two parts, the first part does not depend on time and should be delivered completely to the customer, the second part is time-dependent and would be lost if the rival’s arrival time is earlier than vehicle’s arrival time to the customer. A new mathematical model is developed for the proposed problem and for solving it and a simulated annealing approach is used. The small test problems are solved by the SA and the results are compared with obtained results from Lingo software. For large-scale problems, Solomon’s benchmark instances with additional assumption were used and SA algorithm was able to find good solutions in reasonable time.

Norouzi et al. (2009) present also a study dealing with a routing problem under competition. In this study, there is no time-window, but still time-dependent constraints. More precisely, the authors propose a mathematical model for a bi-objective open vehicle routing problem in a competitive environment (OVRPC). This problem consists of a VRP for which the routes do not return to depot after the last customer. In addition, it is supposed that the profit made at a customer depends on the time on which it is visited, i.e., if a vehicle visits a customer later than its rival, it will miss a part of its sale. Hence, in order to maximize the profit, the company should serve customers earlier than its rival while minimizing the total length of the routes. The authors propose a multi-objective particle swarm optimization (MOPSO) method, a population-based approach inspired from the behavior of natural group organisms, such as bees, fishes, and birds swarm. The results are compared with the Lingo software using a ε-constraint method on small-sized test problems.

Gupta et al. (2010) study a multi-objective fuzzy vehicle routing problem with time windows and capacity constraints (MOFVRP). The concept of fuzzy logic is used to deal with uncertainty on traveling time between two stops and a genetic algorithm is used to deal with multiple attributes: maximization of customer’s satisfaction grade, minimization of fleet size, distance minimization, and waiting time minimization. To demonstrate the effectiveness of the developed approach, a case study is used. It concerns a bus collection application where students must be picked-up and dropped from/to university in India.

Braekers et al. (2011) consider a full truckload vehicle routing problem with time windows encountered in drayage operations. Loaded and empty container transports are to be performed where either the origin or the destination of empty containers must be determined. The authors show that this problem can be transformed into an asymmetric multiple vehicle traveling salesman problem with time windows (am-TSPTW) and a two-phase deterministic annealing algorithm is developed for solving the problem in which the number of vehicles used is minimized as well as the distance traveled. The first phase of the method consists in minimizing the fleet size and the second, the total distance for the current number of vehicles. Deterministic simulated annealing metaheuristics are used in both phases and the performance of global method is tested on randomly generated instances.

4.2 Vehicle Routing with Several Depots

In multi-depot (MD) problems, the departure and return nodes for each vehicle must be selected among a set of depots. The first case considers uncapacitated depots and leads to the MDVRP. Lau et al. (2009) study a multi-objective version with multiple products for which the aim is to minimize both the total traveling distance and the total traveling time required for all vehicles. They propose a fuzzy logic guided NSGA-II (FL-NSGA-II). The role of fuzzy logic is to dynamically adjust the crossover and mutation rates after consecutive generations. They compare their method with a classical NSGA-II, but also with a strength Pareto evolutionary algorithm 2 (SPEA2) and a micro-genetic algorithm (MICROGA), each time with and without the guide of fuzzy logic. The results show that FL-NSGA-II outperformed other search methods on the tested scenarios.

The second case of MD problems occurs when depots are capacitated and/or when the location of those is a decision variable. Location of facilities and vehicle routing, when studied and solved commonly, constituted the location-routing problem (LRP). Nagy and Salhi (2007) have made a survey on the subject. Since then, some papers have been published on the mono-objective case. Prins et al. (2007) and Duhamel et al. (2010) propose the current best efficient metaheuristics and recently, Belenguer et al. (2011) introduced mathematical models and exact solutions methods but they are still limited to medium-scale instances. Prodhon (2011) also studies a periodic version. However, in the past, multi-objective versions were often discarded. Only Lin and Kwok (2006) addressed the case in which total cost minimization and workload balance were the objectives. Additionally, in this study a version with multi-route consideration was possible during the routing procedure. The authors applied two metaheuristics (tabu search and simulated annealing) on real and simulated data and compared the results of two versions: simultaneous or sequential routes assignment to vehicles. Other papers were published for hazardous transportation, in which apart from the cost, the location and/or a transportation risk have to be minimized to ensure a safety perimeter for the population (List and Mirchandani 1991; Giannikos 1998; Alumur and Kara 2007).

Nowadays, criteria to optimize in addition to the total cost are more related with the demand to be served. Tavakkoli-Moghaddam et al. (2010) present a new integrated mathematical model for a bi-objective version where the total cost (setup cost of the facility, fixed and variable depot costs, and routing cost) has to be minimized while the total demand to be served has to be maximized. The authors propose a multi-objective scatter search (MOSS) algorithm and validate both the solution quality and diversity level on various test problems through some comparison metrics with the elite tabu search (ETS).

In the same vein, an interesting application of multi-objective LRP concerns logistics of relief. Rath and Gutjahr (2011) consider a problem faced after the occurrence of a natural disaster. A supply system with intermediate warehouses has to be established to provide affected people with relief goods. It may happen that total supply is less than total demand. Thus, a three-objective optimization model is proposed. The first objective minimizes the fixed costs for depots and vehicles. The second objective minimizes operative cost (routing and warehousing). The third objective maximizes the covered demand. They apply the ε-constraint method to determine the Pareto frontier and solve the single-objective problem by a metaheuristic technique based on an MILP formulation with a VNS algorithm to iteratively add heuristically generated constraints. Results on generated instances and a real case are compared to those obtained from an application of the NSGA-II metaheuristic.

Coutinho-Rodrigues et al. (2012) also study multi-objective catastrophe responses for urban evacuation paths and location of shelters. Six objectives are considered in an MILP model, including the minimization of total travel distance for all of the population to shelters, the minimization of the risk on paths and at the shelters, and the minimization of the total time required to transfer people from shelter to a hospital. The proposed approach is tested for a simulated fire situation in the historical city center of Coimbra, Portugal. The solutions are compared in the objective space via several graphical techniques.

4.3 Routing Problems with Profit

In routing problems with profits, for each customer a positive profit (score) is given, in addition to the elementary data defining a basic CVRP (graph G). In some variants, a penalty can also be associated to each customer. These kinds of problems permit to visit only a subset of customers and occur in industrial application such as scheduling repairmen visits to the most profitable customers, tourist travel guide systems, etc. This family of routing problems with profits is by nature multi-objective with two opposite optimization criteria. The first objective consists in maximizing the total profit; it hence forces to extend the tour and collect as much profit as possible increasing therefore the traveled distance. The second criterion, in opposition with the first one, instigates to reduce the total traveled distance and consequently tends to visit fewer customers. In spite of the bi-objective nature of this category of problems, the research has been mostly focused on the mono-criterion case.

The variant where only one tour has to be determined is referred to as the traveling salesman problems with profits (TSPP). Feillet et al. (2005) discuss three generic problems derived from the TSPP, depending on how the two objectives are tackled. In the first one, both criteria are expressed in the objective function which consists in minimizing the travel costs minus the collected profit. This problem is called profitable tour problem (PTP). In the second class, the travel costs are expressed as a constraint. The profit is maximized while the length of the tour must not exceed a given limit. This problem is called the orienteering problem (OP). In the third class, the total profit is expressed as a constraint and it must not be less than a given value and the travel costs are minimized. This last variant is referred to as prize collecting traveling salesman problem and often considers penalties on the customers not serviced. The sum of these penalties (when defined) is then added to the total traveled distance to obtain the objective function, which must be minimized.

The team orienteering problem (TOP) is an extension of the orienteering variant to the case where a fixed number (great or equal to 2) of tours must be built. TOP has been defined for the first time by Chao et al. (1996) and is, besides the orienteering variant (OP), the more studied problems among all those cited above. However, most published papers in the literature focus on the mono-objective variants.

The multi-objective version of the TSPP has been considered for the first time in Keller and Goodchild (1988). After this first study, to the best of our knowledge, only four journal papers have been published. The first is from Riera-Ledesma and Salazar-González (2005) who study the traveling purchaser problem, in which the nodes represent markets of different products. The traveling purchaser must visit a subset of markets in order to purchase the required quantity of each product while the travel cost and the purchase cost are both minimized. In Jozefowiez et al. (2008a), an ejection chain local search enhanced within a multi-objective evolutionary algorithm is developed to generate efficient solutions to the traveling salesman problem with profits. Bérubé et al. (2009) propose an exact ε-constraint method for the same problem and finally, Schilde et al. (2009) study a new bi-objective variant of the orienteering problem where each customer is associated with two different values of profit. The two objective functions considered are the maximization of both kinds of collected profits. The authors propose an ant colony optimization and a variable neighborhood search, hybridized both by a path relinking method, in order to generate Pareto optimal solutions. More recently, Labadie et al. (2011) have designed an NSGA-II based approach to resolve the bi-criteria version of the TOP. In this last study, the aim is to select the set of customers to be serviced and to build a fixed number m greater than one of tours to cover these customers, so as the total profit is maximized and overall traveled distance is minimized.

4.4 Covering Tour Problems

The covering tour (CTP for covering tour problem) generalizes the traveling salesman problem (TSP). It considers a graph G defined as in the CVRP but the set of nodes V is constituted of two complementary subsets V 1 and V 2. The first (V 1) contains the set of nodes that can be visited and contains some vertices which must be included in the solution. The second set (V 2) encloses nodes that must be covered. In addition to these data, a covering distance L is given. The problem aims to build a tour with a minimal length visiting a subset of nodes from V 1 such that all nodes in V 2 are covered. A node v is said to be covered if and only if there exists at least one node in the tour such that the distance separating it from v is less than L. As for the TSP with profits, the covering tour is clearly identified by Boffey (1995) as a multi-criteria problem.

The maximal covering tour problem is a bi-criteria variant of CTP introduced by Current and Shilling (1994). In this problem, for each node to cover in V 2 is associated a demand and the aim is to build a tour containing exactly p nodes from V 1 (with p ≤ | V 1|), such that the total demand covered is maximal and the cost (or length) of the tour is minimal. In this variant, a node v is said to be covered if and only if its demand is satisfied by a node in the tour contained in the circle whose center is v and radius is L. Such problems are encountered in mobile service delivery systems such as health care delivery in the rural areas of developing countries and in disaster relief supplies where the aim is to ensure the delivery of a large amount of emergency supplies such as food, water, and medicaments to some center points from which the supplies would be distributed to others disaster zones. For a recent survey on covering problems see Farahani et al. (2012), a subsection is dedicated to the problems already mentioned.

Besides the paper of Current and Shilling (1994) in which a heuristic is proposed to generate an approximation of the Pareto front, another study from Jozefowiez et al. (2007) dedicated to the bi-objective covering problem is also available in the literature. In this last paper, the constraint requiring exactly p nodes in the tour is relaxed and the covering distance imposed in the CTP becomes an objective. The problem studied deals with the minimization of the tour cost and the minimization of the cover. The cover of a solution is defined as the maximal distance between nodes which must be covered (nodes in V 2) and their closest nodes included in the tour. The authors have proposed a two-phase cooperative strategy that combines a multi-objective evolutionary algorithm with a branch-and-cut algorithm initially designed to solve a single-objective covering tour problem. The numerical tests are carried on randomly generated instances and real data (data of the Suhum district, east region of Ghana) and the results are compared to those obtained by a bi-objective exact method based on an ε-constraint approach with a branch-and-cut algorithm.

More recently, Tricoire et al. (2012) have studied the bi-objective covering tour problem with stochastic demands. The two considered criteria, both to minimize, are the total cost (opening cost for distribution centers plus routing cost for a fleet of vehicles) and the expected uncovered demand. The authors assume that depending on the distance, a certain percentage of clients goes from their homes to the nearest distribution centers. To compute solutions of the two-stage stochastic program with recourse, a branch-and-cut technique is used within an ε-constraint algorithm. Computational results on real-world data for rural communities in Senegal show the viability of the approach.

Some other studies have appeared recently in the literature and are dedicated to humanitarian logistics and disaster relief optimization where often several conflicting criteria are to be taken into account. In those studies, one is often faced to the resolution of some variants of the covering tour problem. For instance, the study from Viswanath and Peeta (2003) deals with a multi-commodity maximal covering network design problem for identifying critical routes for earthquake response. The problem is formulated as a two-objective (minimizing the total travel time and maximizing the total population covered) integer programming model that is solved with a branch-and-cut. The search for the critical routes for an origin–destination pair is confined to a limited geographical region to reduce the computational time.

Tzeng et al. (2007) propose a multiple objective relief-distribution model with objectives based on the effectiveness (through the minimization of the total cost and the total travel time) and fairness (by maximizing the minimal satisfaction during the planning period) of the overall distribution system. Results of an empirical study are presented.

Nolz et al. (2010) study a multi-vehicle covering tour problem that consists of routing and placement of tanks of water to cover all beneficiaries rather than being transported directly to them. Two objectives are targeted: the first is related to distances between population and distribution points, and the second is related to cost of the chosen tour.

Vitoriano et al. (2011) add another important aspect when dealing with humanitarian problems that is the reliability of the routes. Hence, they proposed to extend the bi-criteria approach proposed in the previous works dedicated to humanitarian aid distribution problems, by considering a multi-criteria optimization model based upon cost, time, equity, priority, reliability, and security. More specifically, the problem is described through a transport network with pick-up, delivery, or connection nodes and arcs characterized by distance, average velocity and reliability, heterogeneous fleet of vehicles, operation elements such as the global quantity to be distributed and the budget available. The problem is not formulated exactly as a covering tour problem, but the proportion of satisfied demand at a specific node is considered. A goal programming model is presented and applied to the Haiti earthquake that happened in 2010.

5 Multi-criteria Path, Flow, and Network Design

In some kinds of extension to the multi-depot case, routing problems aim at finding the paths from some origin positions to destination points. Such examples can be found in supply chain or multi-modal transportation. First, let us consider the case of finding the optimal transit only between two nodes of a network. In the single objective case, this problem is referred to as the shortest path problem and has been intensively studied in the literature. Practical applications such as routing in railways networks often show the necessity to compute the shortest path with respect to several criteria such as traveling time minimization, waiting time, or number of transit points. The interested reader on such problems can see the survey from Skriver (2000).

In more recent researches, Raith and Ehrgott (2009) considered the bi-criteria shortest path problem where two kinds of costs are associated with each link in the network. The aim is to compute a path linking an origin point to a destination point such as both overall total costs are minimal. The authors compare several strategies to resolve the problem on grid, random, and road networks. They deduce that the two-phase method is competitive with other commonly applied approaches to solve the bi-criteria shortest path problem and that the two-phase method works well when combined with both a ranking, a label correcting, and a label setting approach in the second phase. However, the tests show that the label correcting and setting approaches are preferable as they are more stable and, although very efficient on some instances, enumerative near shortest path approach is much time-consuming on others. In the same year, another study from Pinto et al. (2009) was developed for the tri-criterion shortest path problem with two bottleneck objective functions (MinMax, MaxMin for instance) and a cost function. An algorithm able to generate a set of Pareto-optimal paths is proposed and the authors show that bottleneck functions with finite number of values lead to algorithms with polynomial complexity. Then, Pinto and Pascoal (2010) have proposed an improved version of the algorithm appeared in the previous paper. Although both algorithms have the same worst case complexity, the improved version is able to improve the running time on randomly generated benchmark.

Ghoseiri and Nadjari (2010) are also involved in this issue. They present an algorithm based on multi-objective ant colony optimization (MOACO) and propose experimental analyzes on randomly generated instances with two objective costs to minimize. Compared with results of label correcting solutions (the most known efficient algorithm for solving this problem) on the Pareto optimal frontiers, the suggested algorithm produces good quality non-dominated solutions and time saving in computation of large-scale bi-objective shortest path problems.

Reinhardt and Pisinger (2011) also focus on the multi-objective shortest path problems and give a general framework for dominance tests. This is particularly useful to eliminate paths in a dynamic programming framework when using multiple objectives. The authors report results on instances based on the data of a shipping company with several nonadditive criteria such as the time, the number of transfers, the cost, or the probability of reaching the destination.

The studies of Mora et al. (2013) and Tezcaner and Köksalan (2011) deal with military logistics and concern also multi-objective shortest path design. The first is dedicated to solve a path finding problem considering two objectives: maximization of speed and safety. To solve it, three versions of MOACO algorithms, globally identified as hCHAC and dealing with a different number of objectives (two, four, and just one in an aggregated function) are designed. A different parameterization set has been considered in each case. The hCHAC algorithms are tested in several different (and increasingly realistic) scenarios, modeled in a simulator and compared with other MOACOs. Two of them are well-known state-of-the-art MOACOs and the third is a novel multi-objective Greedy approach used as a baseline. The experiments show that most of the hCHAC algorithms outperform the other approaches, yielding at the same time very good military behavior in the tactical sense. Within the hCHAC family, the approach considering two objectives yields the best results overall. The second study by Tezcaner and Köksalan (2011) addresses the route selection problem for unpiloted aircrafts called unmanned air vehicles (UAV). The problem consists of visiting several targets before returning to the base. Determining a good route in such a case may mean to minimize the total distance traveled and maximizing radar detection threat. However, contrary to classical TSP, there is not a single path between any two consecutive nodes but multiple possible paths. Therefore, the problem turns into a combination of an interrelated multi-objective shortest path problem and an multi-objective traveling salesman problem (MOTSP). The authors develop an exact interactive approach to identify the best paths and the best tour of a decision maker under a linear utility function.

Shimamoto et al. (2010) study a problem for which paths have to be found for various origin and destination nodes of the graph. More specifically, they analyze an existing bus network. In this case, there is no product to ship but the model has to consider the passengers’ behavior. To do so, it is formulated as a bi-level optimization problem. The upper problem minimizes costs for both passengers (total travel cost) and operators (total operational cost) while the lower problem deals with the transit assignment. An NSGA-II is proposed to solve a study case on demand data from Hiroshima City.

When deliveries have to be made through a supply chain, the aim might be to design the distribution network. Cintron et al. (2010) describe a multiple criteria mixed-integer linear program to determine the optimal configuration of the manufacturing plants, distributors, and customers in a distribution network and to design the flow of products in this system. In other words, for each customer the model chooses the best option for receiving products based on several criteria: profit, lead time, power, credit performance, and distributors’ reputation. The options to supply the products are delivery from (1) the regional distribution center (DC), (2) the manufacturing plant, (3) an independent distributor who is supplied from the regional DC, or (4) an independent distributor who is supplied directly from a manufacturing plant. Tests are performed on real data from a consumer goods company and under multiple scenarios to reflect the variability in demand.

Still working on a supply chain within a three-level logistic network, Rajabalipour-Cheshmehgaz et al. (2013) propose to find compromise solutions through a customized Pareto-based multi-objective evolutionary algorithm, NSGA-II. In this study, the levels are some potential suppliers, distributed centers, and consumers with deterministic demands for a period of time. As in Cintron et al. (2010), some flexibility is possible with potential direct shipments from suppliers to consumers. This is motivated here by the option of capacitated facilities (suppliers and distributed centers). So the problems are formulated into four individual logistic network models varying with the flexibility option and/or the capacitated facilities. The main objective is to calculate the status (open or close) of facilities and transportation links in order to minimize the response time to consumers, the transportation cost, and the facility costs, simultaneously and without considering prior knowledge, through the seasonal network (re)design.

Marjani et al. (2012) consider a supply chain in which distribution centers operate as transfer points (cross-docking) to obtain a least storage all along the system. The coordination of cross-docks is then crucial. The authors considered multi-type and time-restricted pickups and deliveries, transshipment possibility among cross-docks and tardiness permission for some pickups. They modeled the distribution planning problem of the cross-docking network through a bi-objective integer programming model minimizing total transportation and holding costs and total tardiness. They also propose a heuristic procedure to construct an initial solution and three frameworks based on variable neighborhood search, tabu search, and simulated annealing, respectively.

Concerning problems dealing with transfer points, a particular case is the multimodal transport, i.e., routes performed by at least two different means of transport. Androutsopoulos and Zografos (2009) study the determination of non-dominated itineraries when paths enhanced with scheduled departures have to be made in a multimodal network with time-dependent travel times. The authors propose to decompose the problem into elementary itinerary subproblems, solved by a dynamic programming algorithm. Si et al. (2011) work on urban multimodal traffic network and study environmental pollution and energy consumption for such a system, in addition to minimizing the total travel time. The multi-criterion system optimization problem also dealt with factors, such as travelers’ convenience which influence their behaviors. A bi-level programming model is proposed, in which the multi-objective optimization model is treated as the upper level problem and a combined assignment model to manage to convenience is processed as the lower level problem. The solution algorithms are given through a single numerical example.

Finally, a mixed between the shortest path, the bus routing and the multi-modal problems, is considered by Artigues et al. (2011). They propose several label setting algorithms for computing the itinerary of an individual in urban transportation networks. Mode restrictions are considered under the concept of viable path, modeled by a non-deterministic finite state automaton (NFA). The aim is the minimization of the travel time and of the number of modal transfers. They show that this bi-objective problem is polynomial in both the number of arcs and nodes of the transportation network and the number of states of the NFA. They also propose dominance rules that allow reducing significantly both the CPU times and the number of visited labels for all algorithms. Tests of their algorithms are performed on a realistic urban network and on an expanded graph.

6 Classification of the Literature

This section is dedicated to the summary of the bibliographical review on multi-criteria routing problems. As said before, we are only aware of two published surveys on the subject: Boffey (1995) and Jozefowiez et al. (2008b). Thus, the papers listed here are mainly the ones which have been published over the last half-decade.

Real-life routing problems often consist of a large number of different constraints and objectives; this makes difficult their classification into any specific group of VRPs. Several academic studies listed in the previous sections have aspects that relate them to real-life cases since they have included complex constraints and/or objective functions. The classification proposed here is made through four tables (Tables 1.1, 1.2, 1.3, and 1.4), one per main group of routing problems, giving an overview of the published papers which are presented in an ascending chronological order.

Table 1.1 CVRP/CARP and its time constrained variants
Full size table
Table 1.2 Vehicle routing with several depots
Full size table
Table 1.3 Routing with optional services (Covering tour-routing with profits)
Full size table
Table 1.4 Path, flow, and network design
Full size table

In each table, the first column provides the authors and the publication year of the mentioned paper, so that the interested reader can easily refer to the bibliography section. The second column specifies the problem under consideration. Column 3 recalls the objective functions, with minimize and maximize. Finally, the last column indicates the approach used to solve the problem.

Table 1.1 contains the main publications on classical routing problems and their variants, the most investigated in multi-objective optimization concerning time constrained attributes. This group is the largest with 14 papers. Table 1.2 is dedicated to routing problems with depots. Such kinds of problems are less studied, but this is not surprising since the same is also observed in the mono-objective version. Table 1.3 encloses particular routing problems in which all the customers do not need to be visited. Finally, Table 1.4 covers some extra problems encountered in logistics and involving routing decisions.

Across these tables, an interesting feature clearly appears. A number of the latest papers are dedicated to relief/military contexts or are at least related to a service to maximize; these are marked by a double asterisk (**) in front of the author names. This feature is mainly true for routing problems with optional services since they can be naturally closer to such concern, but also for routing with depots. On the contrary, no reference on this kind of issue is quoted in Table 1.1. However, in an interesting paper, Campbell et al. (2008) propose methodologies to deal with two unusual objective functions for a TSP and a CVRP: one that minimizes the maximum arrival time and the other that minimizes the average arrival time. These criteria are very relevant in a disaster relief context. Even if this is not a multi-objective optimization, the aim of the paper is mainly to show how much impact new objective functions could have on the solutions through approaches based on insertion and local search techniques. Results underline the significant improvements in service to population affected by the disaster.

7 Conclusion

This work aims to survey the literature dedicated to routing problems and focusses mainly on works which appeared after the review made by Jozefowiez et al. (2008b). We classify the studies on main categories of routing problems clearly identified as multi-objective ones. For some works, when it is not easy to make this classification, we try to keep connection on the different variants presented. Therefore, four main categories are proposed: (1) classical routing problems and their variants concerning time constrained attributes, (2) routing problems with depots, (3) routing problems in which all the customers do not need to be visited, and (4) some extra problems encountered in logistics involving routing decisions.

Over the last half decade, one can observe a growing attention to multi-criteria routing problems. This is due to their numerous real applications and there is still much work to do toward both applications and methodologies. Considering the current state of the literature, we recognize at least two emergent and interesting application fields to be more explored: (1) the first concerns routing problems in military, disaster relief and humanitarian logistics which, in our opinion, disserves more research in the next years; (2) the second research direction can be oriented toward routing problems in logistics related to the service sector, such as for example maintenance and bus routing problems, where a compromise has to be made between routing costs and the quality of the service.

When examining the summary presented in this review, one can see that most of the developed approaches are based on multi-objective genetic algorithms. The reason that such resolution methods are often chosen is, in our opinion, due to their proven performance on previous studies dealing with combinatorial problems and also due to their ease of implementation. Other metaheuristics known to be efficient in solving vehicle routing problems, such as tabu search or large neighborhood search, must be explored in-depth to adapt them efficiently to the multi-criteria case.