LITERATURE REVIEW ON THE VEHICLE ROUTING PROBLEM IN THE GREEN TRANSPORTATION CONTEXT

Eliana M. Toro O.¹

Antonio H. Escobar Z.²

Mauricio Granada E.³

Recibido el 13 de septiembre de 2014, aprobado el 1 de abril de 2015 y actualizado el 11 de noviembre de 2015

DOI: 10.17151/luaz.2016.42.21

ABSTRACT 

In the efficient management of the supply chain the optimal management of transport of consumables and finished products appears. The costs associated with transport have direct impact on the final value consumers must pay, which in addition to requiring competitive products also demand that they are generated in environmentally friendly organizations.

Aware of this reality, this document is intended to be a starting point for Master’s and Doctoral degree students who want to work in a line of research recently proposed: green routing. The state of the art of the vehicle routing problem is presented in this paper, listing its variants, models and methodologies for solution. Furthermore, the proposed interaction between variants of classical routing problems and environmental effects of its operations, known in the literature as Green-VRP is presented. The goal is to generate a discussion in which mathematical models and solution strategies that can be applied within organizations that consider within their objectives an efficient and sustainable operation are posed.

KEY WORDS: Heuristics for the vehicle routing problem, vehicle routing problem, Emission estimation techniques, green transportation

REVISIÓN DE LA LITERATURA DEL PROBLEMA DE RUTEO DE VEHÍCULOS EN UN CONTEXTO DE TRANSPORTE VERDE

RESUMEN

En el gerenciamiento eficiente de la cadena de suministro aparece la gestión óptima del transporte de insumos y productos terminados. Los costos asociados al transporte tienen impacto directo sobre el valor final que deben pagar los consumidores, que además de requerir productos competitivos también exigen que los mismos sean generados en organizaciones amigables con el medioambiente.

Consientes de esa realidad este documento pretende ser un punto de partida para estudiantes de maestría y doctorado que quieran trabajar en una línea de investigación propuesta recientemente: el ruteo verde. En este trabajo se muestra un estado del arte del problema de ruteo de vehículos, enumerando sus variantes, modelos y metodologías de solución. Además, se presenta la interacción que se ha propuesto entre variantes clásicas de los problemas de ruteo y los efectos ambientales de su operación, denominados en la literatura como Green-VRP. El objetivo es generar una discusión donde se planteen modelos matemáticos y estrategias de solución que puedan ser aplicadas en organizaciones que consideren dentro de sus objetivos una operación eficiente y sustentable.

PALABRAS CLAVE

Heurísticas para el problema de ruteo de vehículos, problema de ruteo de vehículos, técnicas de estimación de emisiones, transporte verde.

1. INTRODUCTION

Today the world population is nearly 7 billion people and is projected to reach 9 billion by 2040. An important component of the middle class population is characterized by its size and the high requirement level of a variety of resources. According to forecasts, this segment of the population will increase by 3.000 million in the next 20 years, which will increase the use of the requested resources exponentially.

In 2012, the Panel on Global Sustainability of the United Nations (UN) drew attention to an important fact: The world requires ensuring their global needs. These needs are essentially water, food and energy. There is however one aspect of great relevance overlooked and that is related to the ongoing pursuit of social welfare: mobility. The little planned road infrastructure and uncontrolled vehicles incorporating this infrastructure, growth leads humanity to a global gridlock. To date has nearly 2000 million vehicles, according to Ford projections, in 2040 will be 4 billion. 75% of the world population will live in towns and cities there will be about 50 to more than 10 million.

Global gridlock directly affects the quality of life of city dwellers. The proposed solution to this problem necessarily pass through aspects such as: 1) Service Management (solid waste collection, definition of emergency routes, logistics distribution plans and gathering); 2) supply chain (transport of inputs and goods); 3) urban transport planning and 4) transportation of workforce serving various support services, such as in the case of gas companies, electricity and water supply. A distribution company as well as public transportation company requires managing their fleet supported by a set of associated equipment and services.

The problem of transport of goods, commodities and people is as relevant as when it was raised in 1959 by Dantzig and Ramser (1959), where it was considered as a generalization of the traveling salesman problem. The first article in which the phrase “Vehicle routing” appeared is attributed to Golden et al (1972)  ). Other versions of Vehicle Routing Problem (VRP) appeared in the early 70s. Liebman and Marks (1970) presented mathematical models that represent routing problem associated with the collection of wastes; Levin (1971) posed the problem of fleet vehicles; Wilson et al. (1971) presented the problem of telephone request for transportation service for persons with disabilities and Marks and Stricker (1971) presented a model for routing public service vehicles. Some probabilistic concepts were associated with the problem by Golden and Stewart (1975). In Solomon (1987) constraints of time windows were included; Sariklis and Powell (2000) proposed a problem where the vehicle does not return to the point where the journey begins. Recently, some specific conditions have been added to approach VRP to real life problems, resulting in several variants which modify constraints or the objective function of the basic VRP optimization model.

The purpose of this paper is to present the state-of-the-art of VRP considering it is an important supply chain element. Separate the problem into categories, considering different situations, mathematical models and solution techniques. In addition a review of the techniques used in the calculation of fuel consumption and the way to involve it to the VRPs, which has led an interesting area of research Green-VRPs.

The paper is organized as follows: In section 2 the importance of transportation in the supply chain is presented. Next, in section 3 the VRP is classified. The mathematical models are described in section 4. Further, the solution techniques are listed in section 5. An overview of emission estimation techniques is shown in section 6. Finally trends and future directions in Green VRP are presented in section 7.

2. IMPORTANCE OF TRANSPORTATION IN THE SUPPLY CHAIN

In recent years, consumers, businesses and governments have increased their attention to the environment. Society is more aware of the environmental damage caused by human activity and is more concerned about the indiscriminate use of natural resources. A growing interest is also seen by companies to reduce the environmental impact of their products and services (Quariguasi et al., 2009).

The chain management “green” supply has been defined as:

[…] the integration of environmental thinking within the administration of the supply chain, including design, selection of sources of raw materials, manufacturing processes and product delivery end consumers as well as the administration of the products when they end their life. (Srivastava, 2007,p. 54)

Interest in this area has increased significantly in business, for employees of organizations, governments and benefits companies looking to implement “green” supply chain , including cost reduction, improved product and process quality, risk reduction and improving financial performance (Vachon and Klassen, 2008; Sarkis, Zhu and Lai, 2011).

With regard to the environment, transportation is one of the most visible within the supply chain aspects. The amount of carbon dioxide (CO₂) emissions from transport is calculated at 14% of total emissions. Transport is also the main source of nitrogen dioxide (NOx), sulfur dioxide (SO₂) and other particles (McKinnon and Woodburn, 1996). The results of studies of the most important factors for emissions of carbon dioxide (CO₂) in road transport are presented in Piecyk (2010).

United States has established standards for NOx, SO₂ and PM for trucks based on the standard Euro V, regulated by the European commission, and that is part of a package of measures adopted by the European Parliament in 2007. According to the results studies, the trucks are much cleaner for the environment than most ships and trains. Offshore vessels emit large amounts of NOx. It is estimated that these emissions exceed the total emissions from land transport unless action is taken there on Dekker, Bloemhof and Mallidis (2012).

Transportation modes (e.g. Airplane, boat, truck, train, barge or pipeline) have different characteristics in terms of cost, transit time, accessibility and environmental performance. In Leal and D’Agosto (2011) a method for selecting the mode of transport, applied to the transport of bio-ethanol in Brazil is presented, this is an adaptation of the methodology called MCM (The Modal Choice Method). Some questions to be addressed in the “green” supply chain are: how much does it improve the environment? How to balance environmental concerns and profitability in business? The so-called eco-efficient solutions show that additional efforts are required to improve the quality of the environment.

3. VEHICLE ROUTING PROBLEM

In its general form the objective of the VRP is to design a set of minimum cost routes that serves a number of places, geographically dispersed, and fulfilling specific constraints of the problem. Since its first formulation in 1959, there have been many publications and has expanded its scope. Initial studies were conducted for analyzing the distribution management. In the last decade there have been significant advances in terms of the technical solution to resolve large instances. Another aspect that has gained interest is the inclusion of technological innovations in the VRP. These include global positioning systems, radio frequency identification and use of high-capacity computer information processing (Ghannadpour et al., 2014).

3.1. Classification of VRP problems

VRP problems can be classified creating taxonomy or creating a generalized framework that summarizes the existing models, the objectives pursued and the theories associated with the analysis of the problem (Reisman, 1992).

Two-Echelon Vehicle Routing Problem (2E-VRP): the goods are delivered from depots to intermediary satellites, also known as intermediate depots, and then to the customers. Crainic et al. (2010 presented analysis about the problem; Perboli and Tadei (2010) showed mathematical models that represents the problem.

symmetric capacitated VRP (ACVRP): The costs of the arcs are asymmetric. Indicates that the cost to travel from consumer i to consumer j is different from j to i. The problem has been solved in different ways, for example Laporte and Nobert (1987) proposed an exact algorithm, Vigo (1996) presented a heuristic algorithm; Pessoa, Uchoa and Aragão (2008) proposed a robust Branch and Bound Algorithm.

Arc Routing Problem (ARP): It must find the shortest route through all the paths and return to its starting position. Applications: garbage collection, reading utility. Models relaxations and exacts approaches can be found in Toth and Vigo (2002). Lancomme, Prins and Ramdane (2001) have solved the problem  using Genetic algorithms. Martinelli, Poggi and Subramanian (2011) have posed new bounds for large scale instances.

CVRP (Capacitated Vehicle Routing Problem): It takes into account the vehicle capacity. The nodes are assigned specific demands. Baldacci and Mingozzi (2004), Baldacci, Toth and Vigo (2010)solved the problem using  exact algorithms (, .

Dial-a-ride Problem (DARP): this problem is modeled to represent the transportation for the elderly, disabled, ambulances used in regular services, animals and goods, time sensitive transportation, taxis, courier service. The following authors presented papers in this topic: Cordeau and Laporte (2003) presented DARP state of the art, Cordeau (2006) solved the problem with   a Branch and Cut algorithm -- Jorgensen and Larsen (2006) proposed a Genetic algorithm --- to solve the problem.

Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP): For each route, capacity restriction is replaced by a maximum length or by a time constraint. Kara (2010, 2011) presented integer programming formulations.

The Emissions Vehicle Routing problem (EVRP): The minimization of emissions and fuel consumption is the main objective or part of generalized cost function. The VRP considering environmental pollution has also been called Pollution routing problem (PRP)by Bektas and Laporte( 2011), Fuel consumption routing problem (FCVRP) byXiao et al., (2012), Green Vehicle routing problem by Erdogan and Miller-Hooks( 2012).

Generalized VRP (GVRP): In this variant the clients are divided in clusters. If a client is attended, then it is considered that the whole cluster is attended. Applications in communications and distribution networks have been reported. Formulations can be found in Ghiani and Impronta (2000); strategy of solution based on Ant Colony Optimization (ACO) in Pop, Pintea and Zelina (2008). Baldacci, Bartolini and Laporte (2010) presented an exhaustive survey on GVRP and its applications.

Location Routing Problem (LRP):In this problem are solved three problems simultaneously : location of depots, definition of routes and assigning routes to opened depots. . Prins et al.(2007)  solved the problem using Lagrangiean relaxation with granular search .Escobar, Linfati and Toth (2013); Contardo, Cordeau and Gendron, (2014) have solved the problem using matheuristics 3. Recently Prodhon and Prins (2014) analyzed all available  literature about this variant of VRP and proposed new searching lines in this direction.

Multi-Depot Vehicle Routing Problem (MDVRP): In this variant several depots are considered to serve clients. Clients are usually assigned to depots using  clustering strategies. Some solution techniques have been used in this problem for exampleRenaud et al (1996), Salhi and Sari (1997) solved the problem with heuristics.;  Ombuki-Berman and Hanhar  (2009) with Genetic Algorithms (). Vidal et al. (2014) presented a new state of the art results for MDVRP and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size.

OVRP (Open VRP): The goal of the OVRP is to design a set of Hamiltonian paths (open routes) to serve  customer demand. Applications: delivery of school meals, school bus routing, the home delivery of packages and newspapers trains, among others. Li, Golden and Wasil (2007) provided a survey on the algorithms for solving OVRP. Li, Leung and Tian (2012) proposed a multi-start adaptive memory based  Tabu Search algorithm for the heterogeneous fixed fleet open vehicle routing problem.

Periodic Vehicle Routing Problem (PVRP):  In this problem is considered the deliveries to customer done on certain days of the week.  Hemmelmayr and Doerner (2009); Cacchiani, Hemmelmayr and Tricoire (2014)has been solved the problem successfully using heuristics ().

Real time dynamic VRP (RTDVRP): Extension of VRPTW, consider traffic conditions. Vehicle dynamic allocation. Ghiani et al. (2003) presented algorithms and parallel computing strategies. Giagli et al. (2004) presented mobile technologies applied to the problem.

Split Delivery VRP (SDVRP): Each customer is required to be visited by exactly one vehicle and the objective is to minimize the total distance traveled. The restriction that each customer has to be visited exactly once is removed, split deliveries are allowed. Archetti, Savelsbergh and Speranza (2006) presented a survey of the state-of-the-art. Wilck IV and Cavalier (2012)have posed  a construction heuristic.

Stochastic VRP (SVRP): Stochastic Modeling of at least one of its variables: on set and / or customer demand. Bertsimas (1992) analyzed the problem using a variety of theorical approaches and proposed heuristics like re-optimization strategy. A Tabu Search heuristic was proposed by Shen, Ordóñez and Dessouky (2009). An important application is the distribution of medical supplies to respond to large-scale emergencies such as natural disasters or terrorist attacks.

Time Dependent VRP (TDVRP): Travel time between two customers or between a client and the deposit depends on the distance between the points and the time of day is considered. Malandraki and Daskin (1992) presented a state of-the-art; Donati et al. (2008) used ACO to solve the problem.

CVRP on trees (TCVRP): Consists of determining vehicle collection routes starting and ending at the depot, such that: the weight associated with any given vertex is collected by exactly one vehicle. This type of problem can be found on railway lines, rivers, and rural road networks. The problem was formulated and solved through heuristics in the paper presented by Labbé, Laporte and Mercure (1991) and solved by exact way in Mbaraga, Langevin and Laporte (1999).

Truck and Trailer routing Problem (TTRP): The truck and trailer routing problem (TTRP) is a variant of the well-known vehicle routing problem (VRP). Different from the VRP, in the TTRP, customers are serviced by a fleet of trucks and trailers. Due to some practical constraints, some customers can only be serviced by a single truck. The other customers can be serviced by a single truck or a truck pulling a trailer. A heuristic approach was present by Caramia and Guerriero (2010); Villegas et al. (2010) presented a hybrid metaheuristic.

Vehicle routing problems with backhauls (VRPB): Includes both a set of customers to whom products are to be delivered, and a set of vendors whose goods need to be transported back to the distribution center. Wade and Salhi (2003) presented an Ant algorithm for solving the problem. García-Nájera (2012) presented a multi-objective strategy for VRPB.

VRP with heterogeneous fleet (VRPHE): Fleet of vehicles of different capacities. Sometimes considered or not fixed costs and / or variables in the fleet.  Lima, Goldbarg and Goldbarg (2004)  presented a memetic algorithm to solve the problem. (). The problem considering time windows was  solved by Paraskevopoulos et al. (2008). Kwon, Choi and Lee (2013) solved the problem considering carbon emissions.

Vehicle Routing problem with multiple routes (VRPM): Consists in determining the routing of a fleet of vehicles where each vehicle can perform multiple routes at a specific time horizon. It is relevant in applications where the duration of each route is limited; it can found when perishable goods are transported. Olivera and Viera, (2007)have solved the problem using Adaptative memory programming (). Azi, Gendreau and Potvin (2010) proposed an Adaptative Large Neighborhood Search to solve VRPM.

VRP with Pick Up and Delivery (VRPPD):  Is defined over a net. Where some nodes represent delivery customers who expect deliveries from a depot, and other nodes represent pickup customers who have available supply to be picked up and transported to a depot Nagy and Salhi (2003) proposed different algorithms for solving the problem. The most cited article is Chen and Wu (2006) in this work the problem was solved using hybrid heuristics. Subramian et al. (2010) proposed a parallel heuristic.VRP with time deadlines (VRPTD): In this problem, the travel times are not fixed but rather depend both on the distance between two vertices and the time of the day (e.g., it takes longer to get from one location to another during rush hours). The contribution of this variant is more closely modeling situations observed in the real world. Thangiah, Vinayagamoorty and Gubbi (1993) solved the problem with genetic and local algorithm; Özyurt, Aksen and Aras (20065) performed a state of the art of VRPTD.

VRP with time windows (VRPTW): The aim is to serve all customers in a defined time interval. Solomon (1987) presented solutions, methods and applications. In Solomon (1987) the design and analysis of algorithms for vehicle routing and scheduling problems was considered with time window constraints. In this work were found several heuristics with performed well in different variants of VRP. Bräysy and Gendreau (2005) presented a complete review of metaheuristics applied to the problem. Lau, Sim and Teo (2003) proposed Tabu search by a holding list and a mechanism to force dense packing within a route.

VRP with Private Fleet Common Carrier (VRPPC): In this problem the clients can be served either by its own fleet of vehicles or assigned to an external common carrier. The worst case occurs if the demand exceeds the total capacity of the own fleet or if it is more economical to do so with external fleet. Naud and Potvin (2009) provided a Tabu Search with ejections chains to solve VRPPC; Euchi, Chabchoub and Yassine (2011) used an evolutionary algorithm for addressing VRPPC.Vehicle Scheduling-routing Problem (VSRP): The problem is solved in two stages: the definition of routes and other allocation of crews to routes. Thompson and Psaraftis (1993) presented neighborhood search algorithms named cyclic transfer algorithms. Qiu et al. (2002) presented some algorithms for solving the problem considering automatic guided vehicles. Minocha, Tripathi and Mohan (2011)  proposed an algorithm which incorporates a local search technique with genetic algorithm approach to solve VRPTW, because VRPTW is an example of scheduling in constrained environment.  VRP and scheduling with time window (VRSPTW): In the objective function, the costs include a timeout variable when a vehicle arrives too early to a location. Koskosidis, Powell and Solomon (1982) presented a heuristic for addressing the problem. One of the most important works in this topic it is developed by Solomon (1987).

These types of problems are in turn other variants that consider aspects such as scenarios properties and physical characteristics.

Scenario properties: Number of stops on the route, constraints associated with the partition of the load, deterministic or stochastic quantities by customer demands, time required by consumers, service sites, waiting times, structure time windows, time horizon, node types (supply demand, or both) and consideration of environmental effects.

Physical characteristics of the problem: Design transport network, allowed for bows orientation (unidirectional or bidirectional), the location of customers (nodes or edges), number of deposits, number and types of vehicles available, capacity constraints, travel time, travel costs, elements (people, animals, boxes, etc.) are transported.

VRP has been studied in a wide variety of publications.  Bodin (1974) presented the taxonomic structure of the problem  without considering actual demands. Bodin and Golden (1981) described a taxonomy of  routing and assignment problems in that ranking 13 features are proposed. Laporte (1992)  introduced a classification of exact methods split into three categories i) direct tree search methods, ii) dynamic and iii) Integer Linear Programming. Fukasawa et al. (2004) presented a Robust branch-and-cut-and-price for the  CVRP. Sbihi and Eglease (2007) .presented an introduction to Green Logistics issues that are relevant to vehicle routing and scheduling including discussion of the environmental objectives that should be considered.

Yeun et al (2008) presented a review of the state-of- the- art from 1986 to 2006  which includes VRPTW, CVRP VRPPD and problems. Eksioglu, Vural and Reisman (2009) presented VRP nomenclature, incorporating all its variants and associated with the available literature to date. In Kumar and Pannerselvam (2012), the main variants of the CVRP and VRPTW problem framed in the supply chain are presented, the contributions of different authors are classified into three categories heuristic, metaheuristic and hybrid methods. Finally Vidal et al. (2013) analyzed in detail 64 successful metaheuristics applied to 15 variants of VRP, primarily identifying the algorithm design and its main characteristics in terms of: the solution space, neighborhood strategies, search paths, mechanisms control memory, hybrid strategies, and parallelism and decomposition problems.

4. MATHEMATICAL MODELS

VRP can be modeled in different forms. Such as Vehicle Flow Formulations (VFF), Commodity Flow Formulations (CFF) and Set Partitioning Formulation (SPF). These basic models can be modified to reach a specific VRP.

VFF: This formulation is weak in the presence of a hard constraints model. It is useful when you must perform assignments of vehicles to routes. The number of variables is polynomial and number of constraints is exponential.

A            Set of arcs

V            Set of vertices

S             Set of clients

c_ij           non negative cost

K             Number of vehicles available

X_ij          Binary variable activated if the arc i, j is used.

VFF: The CVRP can be described as a theoretical problem in graph theory. Where G = (V , A) is a complete graph, where V = {0 , ..., n}. The vertices i = 1,..., n correspond to consumers and the vertex 0 corresponds to the depot. If the costs of the matrix C are asymmetric then being scanned ACVRP. Constraints (2) and (3) indicate that exactly one arc enters and leaves each vertex is associated with a consumer. Similarly, constraints (4) and (5) impose the degree of vertex deposit requirement. Capacity-cut constraints (CCCs) expressed in (6) impose connectivity solution with the capacity requirements of the vehicle, they stipulate that each cut defined by S is crossed by a number of not less arcs r(S) (minimum number of vehicles needed to meet the set S). Constraint (7) defines the binary nature of the variables x_ij.

CFF: The graph should be extended to a whole directed graph G = (V', A'). Two new non-negative variables y_ij and y_ji must be added, these variables are associated to each arc i,j belonging to A'. If the vehicle travels from i to j, then y_ij and y_ji, deliver the vehicle load and the residual capacity of the vehicle through the arch respectively, y_ji = C- y_ij. The positions invested in equity if the vehicle travels from j to i. Therefore, the equation y_ij + y_ji = C is maintained for each arc i, j belonging to A'. The flow conservation constraints (9) say that the difference between the sums of the flow of goods associated with the arcs represent the quantities delivered and collected at each vertex i is equal to twice the demand of node i. Constraints (10)-(12) determine the correct values of incident flow of goods within the deposits. Restrictions (13) and (14) correspond to the ratio between the flow vehicle and the goods flow variables and the degree of the vertex, respectively. Constraints (15) and (16) define nature of the variables.

SPP: H = {H1,...,Hq} denotes the collection of circuits of G, each corresponding to a feasible route, with q = |H|. Hj each circuit has an associated cost c_j. Constraint (18) indicates that each user i has to be addressed exactly once by one of the selected circuit, and (19) requires that k circuits are selected. Constraint (20) defines the binary nature of the variables x_ij. (Toth and Vigo, 2002).

Marinakis, Migdalas and Pardalos, 2007 proposed the bi-level formulation where clients are assigned to a single route until the route reaches its capacity or time limit. A new client is subsequently selected as seed clients for a new route and the process continues. A client that has not yet been assigned to a route can be a client-seed and is used to initialize a new route. The objective function of the problem of first level minimizes the sum of the costs for client’s seed from the depot. The objective function of the problem of second level describes the path cost of each vehicle based on the allocation of first-level problem. The model retains all the basic VRP constraints.

5. SOLUTION TECHNIQUES

Solution Techniques can be classified as depicted in Figure 1.

5.1. Exact techniques

The VRP in its different forms, was initially addressed using exact techniques such as Branch and Bound algorithm proposed by Laporte and Nobert (1987); Fischetti, Toth and Vigo (1994) and  Baldacci and Mingozzi (2004), Branch and Cut  considered by Cordeau (2006), Branch and Price was posed byPessoa et al., 2008; Martinelli et al., 2011,and  Branch and Cut and Price proposed by Baldacci et al.,( 2010).

5.2. Heuristics

Heuristics for the VRP are divided into three classes: two phases, construction and iterative improvement.

5.2.1. The two-phase heuristics divide the problem into two stages: customer allocation to route and determination the order of the visit. The iterative improvement receives an initial solution and then another heuristic by inter and intra route movements between customers to explore the solution space.Inside this classification Beasley (1983) proposed the strategy Cluster first-Route second and Routed first-Cluster Second.

5.2.2. Construction heuristics. Construction heuristic starts from an empty solution which is filled considering feasible alternatives. This kind of heuristics includes savings algorithm in two versions parallel and sequential posed by Clar and Wright(1964). Insertion heuristics, the solution is created by inserting customers who have not been assigned to a route proposed by Mole and Jameson (1976); and Laporte et al. (2002).

5.2.3. Iterative improvement heuristics. It is for the betterment of the individual routes, and use concepts such as Lambda exchange, Or - OPT, Van-Breedam Operators, Breedam, GENI and GENIUS, widespread insertions proposed by Gendreau, Hertz and Laporte (2001), cyclic transfers, Cross - exchange neighborhood, which is the generalization three neighborhoods: insert, swap and Two - OPT. A detailed explanation of these techniques is found in Corona (2005).

The improvement heuristics inter-and intra-route are widely used into search in the solutions space of any metaheuristic, because of the importance of these strategies is shown in detail their the philosophy. In Subramanian (2012) these strategies are described graphically and algorithmically. The Figures 2, 3 and 4 are based on this document.

From an initial configuration, Figure 2 (a), the following Inter-route heuristics are applied.

• Reinsertion: a client of your current position is extracted and inserted in a different position. In the Figure 2 (b), the client 6 is extracted from its current position and inserted between the nodes 2 and 3.

• Or-Opt2: two adjacent clients from its current position are extracted and inserted in a different position, without changing the order between them. In this case, the client 6 and the client 7 are removed and reinserted, as seen in Figure 2 (c).

• Or-Opt3: three adjacent clients from its current position are extracted and inserted in a different position, without changing the order between them. In this case, the clients 6, 7 and 8 are removed and reinserted between 2 and 3 customers, as seen in Figure 2 (d).

• Exchange: any two clients are taken within the route and their locations are exchanged. In this case, client 3 and 8 are taken and their positions are interchanged, as shown in Figure 2 (e).

• Reverse: the direction of the route is reversed if the maximum load of the route is reduced. In this case all edges with its inverted address are displayed, as seen in Figure 2 (g).

The Shift and Swap are Intra-route heuristics based on the exchange ג. From an initial configuration, apply the following heuristics:

• Shift (1, 0): a client of the route r₁ is inserted on r₂. For this case, the customer 5 is transferred from a route r₁ to a route r₂, as shown in Figure 3 (b).

• Swap (1, 1): a customer m of the route r₁ is inserted into the r₂ and client n is transferred from r₂ to r₁. In Figure 3 (c), clients 4 and 5 are transferred between routes.

• Shift (2,0): two clients are taken from  r₁ and  are inserted into r₂. For this case, customers 5 and 6 which are in the route r₁ are transferred to r₂, as shown in Figure 3 (d).

• Swap (2, 1): two clients A and B are taken from r₁ and C client from r₂. Clients A and B are introduced on r₂ and client C is located on r₁. For this case, clients 5 and 6 are relocated on r₂ and client 4 is located on r₁ as shown in Figure 3 (e).

• Swap (2, 2): two clients A and B are taken from route r₁ and two clients C and D of the route r₂. Customers A and B are introduced on r₂ and C and D customers are introduced on r₁. For this case, a customer 5 and 6 passes the route r₂ and clients 3 and 4 moves r₁ as shown in Figure 3 (f).

• Crossing: the customer arch linking A with the route B in r₁ and the arc joining the client C and D in r₂ are eliminated. Proceed to add two new arcs: one that customer A to D, and other than a customer B to C. In this case, the arcs (3,4) are removed and (6,56.5) and replaced by arcs (6,4) and (3,5), as shown in Figure 3 (g).

• K-Shift: a customer adjacent of r₁ is taken and these are transferred at the end of r₂. In this case, the clients 6 and 7 of the route r₁ is taken and transferred to the end of the route r₂, as shown in Figure 4.

One of the most successful heuristics is LKH algorithm. Chained Lin-Kernighan is an effective method for obtaining very good TSP solutions, even for large scale problems. Usually produce optimal tours for modest-size instances, with several thousand cities (Helsgaun, 2000).

This heuristic is a variation of the local search depth, which begins with a feasible tour T and from this a neighborhood of tours T₁, T₂, ..., Tn, is explored by changing k arcs of T. k changes are needed to decrease the length of the tour. The process ends when you cannot find improvements and said the tour is k-opt, Lin has studied the cases k = 2 and k = 3, finding solutions to the TSP of very good quality and very short computation. The importance of this heuristics is based that has been used successfully in matheuristics algorithms (Escobar et al., 2013).

5.3. Metaheuristics

Metaheuristics have been adapted and intensively used for solve different variants of VRP. The main types of metaheuristics which have been applied to solve to the VRP are: Simulated Annealing, Determinist Annealing, Tabu Search implemented by Renaud et al., (1996); Prins et al., 2007; Li et al (2012), Genetic Algorithms proposed byLacomme et al. (2001); Jorgensen and Larsen (2006); Minocha et al. (2011), Ant colony optimization was posed by Donati et al. (2008); Pop et al. (2008)), Iterative Location Search proposed by Azi et al. (2010), Variable neighborhood Search implemented by Hemmelmayr and Doerner (2009).

To apply such strategies is necessary to define a sufficiently clear and robust coding that allows representing an alternative solution where the value of the objective function and its feasibility is efficiently calculated for all the configurations.

It is also necessary to identify heuristics that can improve the performance of the technique chosen. It is important to define strategies that deliver quality settings and local search mechanisms that allow for efficient and effective exploration of the solution space. Only the metaheuristics applied to VRP deserve space on multiple items, because many authors not mentioned in this document have made quite creative proposals to improve this methodology type where the performance is evident in the responses and times computer. So the study of the variation of VRP interest requires special attention when a metaheuristic strategy is defined as an alternative solution.

5.4. Matheuristics

This kind of methods consists in hybrid strategies that combine elements of heuristic techniques, metaheuristic techniques and methodologies exact solution as BB, BC and BCP. Here the sub-problems are identified and modeled in exact way then are solved by commercial integer linear programming solver. Dynamic programming or Lagrangean relaxation sometimes is used for this step. This techniques were been used by Prins et al. (2007); Pessoa et al. (2008); Martinelli et al. (2011); Escobar et al. (2013).

6. EMISSION ESTIMATION TECHNIQUES

Unlike other vehicle emissions, the CO₂ is directly proportional to fuel consumption (Romilly, 1999; Hutton, 2002). The emissions of diesel engines vary according to the type and density of diesel used. The standard diesel emits 2.82 kg CO₂/liter and ultra-low sulfur diesel 2.57 kg CO₂/liter. In general, the environmental conversion factors DETR (report, 2000) (Department of Environmental Transport and The regions) claims that diesel exhaust even the ultra-low sulfur diesel correspond to 2.68 kg CO₂/liter. This value is comparable to that established the Australian Office greenhouse, which states that approximately 2.7 kg CO₂/liter (Palmer, 2008).

Regarding the consideration of CO₂ emissions in the vehicle routing problem, there are different approaches that have proposed different methodologies to estimate the value of emissions through unique values present emission estimates based on liters of fuel consumed, others consider the distance and weight carried between two points, vehicle acceleration, slope of the road, etc. These elements are considered within the objectives to minimize or within the constraints to consider. An overview of the publications has addressed the issue presented in Table1.

Haga clic sobre la imagen para ampliarla

According to Table 1, some formulations that calculate fuel consumption are presented. To implement any of these proposals it is necessary to identify the information available to solve the specific case. In several of these studies, formulations presented by the Ministries of Transport of Japan and United Kingdom are considered. .

In Figliozzi (2010) the problem is defined like EVRP. This research considers a function developed by the U.K. Transport Research Laboratory that links emissions and travel speeds (16). This formulation considers also departing time. The volume of emissions generated by traveling from client i to client _j and departing at time b_i is named v_ij(b_i). Alpha values {α_o, α₁, α₂, α₃} = {1,576;-17.6; 0.00117; 36,067} are constant parameters for each type of vehicle, and for other types of vehicles these parameters maybe polynomial terms or their inverses.

slij= denotes the speed at departure time in the time interval l.

dlij= distance between i and j in the time interval l.

Two formulations are present. One of them considers a multiobjective function that includes the costs of vehicles; distance traveled, route durations, and emissions. The emissions term uses equation (21). The other one corresponds a three objective model, the first is minimize the number of vehicles as a primary objective, and distance travelled as a secondary objective without violating time windows, route durations, or capacity constraints, equation (21) is included in this objective. The tertiary objective is the minimization of distance traveled and route duration costs.

In Suzuki (2011) proposed the effect of the speed according to the road gradient. cij is defined like vehicle’s fuel consumption rate (mpg) between nods I and j. Where α0 and α1 represents speed regression intercept and speed regression slope respectively. ϓij is a road gradient factor between I and j. The effect of vehicle payload on mpg for heavy-duty trucks studied by the UK Department for transport can be characterized by the linear function.

Where L is the payload (in pounds), β0 ≥0 is the mpg of a truck when it is empty and β1<0 is the coefficient measuring the loss of mpg caused by an additional pound of payload. yij represents a set of clients yet to be visited when the vehicle is traveling on arc (i, j). li denotes the weight of the load to be delivered to customer i. Using this terms is formuled ᴨij, the payload factor that measures the deviation of a vehicle’s mpg in each arc from the average value based on the payload, as:

Expressions (22) and (24) are used in the formulation of the objective function.

In Xiao et al. (20122013) was formulated a linear function dependent on vehicle load for fuel consumption. Considering the following terms:

Where c0 is the unit fuel cost, dij is the distance from i to j, and xij is a binary variable. r as the set of customers on the route.

xij is a binary variable that takes one value when the arc between clients i,j is used on the route.

7. TRENDS AND FUTURE DIRECTIONS IN GREEN VRP

A review of the state of the art routing problems and its connection with the environmental aspect was conducted, the objective is to motivate researchers from disciplines such as operations research, management science, logistics and environmental sciences at the line of research of green vehicle routing problem.

GVRP literature is still in the theoretical field where idealized models are proposed, the objective is to minimize the gap with real applications that generate opportunities for application in enterprises wishing efficient and sustainable operation.

Based on the above it follows that matheuristics strategies are being used intensively by the excellent performance in results and computational times  . The field of hyper-heuristics is quite rich and promising, and is seen as a strategy to strengthen hybrid strategies because more and more applications require custom algorithms for solving variants from VRPs.

The environmental aspect should be considered in the proposed new settlement of any variant of VRP, because sustainability those organizations should consider when developing their operations. Multiobjective programming is proposed as an interesting alternative to be implemented due to the need to take into account the environmental impact reduction strategy.

According with some authors time windows and customer satisfaction level need to work together because is necessary to find trade-off between the economic cost and the environmental cost in routing problems.

POTENTIAL CONFLICT OF INTEREST

Not applicable.

FUNDING SOURCES

This article is the result of the research project Optimal Solution Of The Vehicle Routing Probelm Considering Environmental Effects. code: 7-13-1. GAOPE Research Group. Assigned by the Vicechancellorship for Research, innovation and outreach of the Technological University of Pereira.

REFERENCES

• Acharya, S. (2013). Vehicle Routing and Scheduling Problems with time window constraints-Optimization Based Models. Int Jr. of Mathematical Sciences & Applications, 3(1). ISSN No: 2230-9888.
• Archetti, C., Savelsbergh, M. and Speranza, M. (2006). Worst-case analysis for Split delivery vehicle routing problems. Transportation Science, 40(2), 226-234.
• Azi, N., Gendreau, M. and Potvin, J. (2010). An Adaptive large neighborhood search for a Vehicle Routing Problem with Multiple Trips. CIRRELT-2010-08.
• Baldacci, R., Bartolini, E. and Laporte G. (2010). Some application of the generalized vehicle routing problem. Journal of the operational research society, 61,1072-1077.
• Baldacci, R., Christofides, N. and Mingozzi, A. (2008). An exact algorithm for VRP based on a the set partitioning formulation with additional cuts. Math. Programming, 115(2), 351-385.
• Baldacci, R. and Mingozzi, A. (2004). A Unified Exact Algorithm For The CVRP Base On A Two-Commodity Network Flow Formulation. OR, 52, 723-738.
• Baldacci, R., Toth, P. and Vigo, D. (2010). Exact Algorithms For Routing Problems Under Vehicle Capacity Constraints. Annals of Operations Research, 175(1), 213-245.
• Beasley, J. (1983). Route first-cluster second methods for VRP. Omega, 1, 403-408.
• Bektas, I. and Laporte, G. (2011). The Pollution-Routing Problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.
• Bertsimas, D. (1992).   A vehicle routing problem with stochastic demand, Operations Research, 40, 574-585
• Bodin, L. (1974). A taxonomic Structure for Vehicle Routing and Scheduling Problems. Computers and Urban Society, 1, 11-29.
• Bodin, L. and Golden, B. (1981). Classification in Vechule Routing and Scheduling Problems. Networks, 11, 97-108.
• Bodin, L. and Sexton, T. (1979). The Subscriber Dial-a-Ride Problem. Final report. U.S. Department of Transportation, Urban Mass Transportation Administration, Washington, D.C.
• Bräysy, O. and Gendreau, M. (2005). Vehicle Routing Problem with time windows, Part II: Metaheuristics. Journal Transportation Science, 39(1), 119-139.
• Cacchiani, V., Hemmelmayr, V. and Tricoire, F. (2014). A Set-Covering Based Heuristic Algorithm For The Periodic VRP. Discrete Applied Mathematics,163(1), 53-64.
• Caramia, M. and Guerriero, F. (2010). A Heuristic Approach For the truck and trailer routing problem. JORS, 61, 1168-1180.
• Chen, J. F. and Wu, T. H. (2006). Vehicle routing problem with simultaneous deliveries and pickups. Journal of the Operational Research Society, 57(5), 579-587.
• Clarke, G. and Wright, J. (1964). Scheduling of Vehicles from a Central Depot a Number of Delivery Points. Operations Research, 12, 568-581.
• Contardo, C., Cordeau, J. F. and Gendron, B. (2014). A GRASP+ILP-Based Metaheuristic for the capacitated routing problem. J Heuristics, 20, 1-38.
• Cordeau, J. (2006). A Branch-And-Cut Algorithm For The Dial-a ride problem. OR, 54(3), 573-586.
• Cordeau, J. and Laporte, G. (2003). The Dial-a-ride problem (DARP): Variants, Modeling Issues And Algorithms. 4OR, 1, 89-101.
• Corona, J. A. (2005). Hiperheurísticas a través de programación genética para la resolución de problemas de ruteo de vehículos. Master Thesis. Instituto Tecnológico de Monterrey.
• Crainic, T., Perboli, G., Mancini, S. and Tadei, R. (2010). Two-Echelon VRP: A Satellite Location Analisis. PROCEDIA Social and Behavioral Sciencies, 2(3), 5944-5955.
• Dantzing, G. and Ramser, J. (1959). The Truck Dispatching problem. Managment Sciencie, 6(1), 80-91.
• Dekker, R., Bloemhof, J. and Mallidis, I. (2012). OR for Green-Logistics-An Overwiev of Aspects, Issues, Contributions and Challenges. Operations Research in Health Care, EJOR, 219, 671-679.
• Demir, E., Bektas, T. and Laporte, G. (2012). An adaptative large neighborhood search heuristics for the pollution routing problem. European Journal of Operations Research, 223, 346-359.
• DETR Circular 02/2000, Contaminated Land: Implementation of Part IIA of the Enviromental Protection Act 1990, 1990. Feb-14-2014. [Online]. Available on http://www.eugris.info/displayresource.aspx?r=4460
• Donati, A., Montemanni, R., Casagrande, N., Rizzoli, A. and Gambardella, L. (2008). Time Dependent VRP With A Multi Ant Colony System. EJOR, 185(3),1174-1191.
• Eilon, S., Watson, C. and Christofides, N. (1971). Distribution Management: Mathematical Modelling and Practical Analysis. London: Griffin.
• Eksioglu, B., Vural, A. and Reisman, A. (2009). Survey: The Vehicle Routig Problem: A taxonomic review. Journal Computers and Industrial Enginnering, 57(4), 1472-1483.
• Erdogan, S. and Miller-Hooks, E. (2012). A Green Vehicle Routing Problem. Transportation Research Part E, 48(1), 100-114.
• Escobar, J., Linfati, R. and Toth, P. (2013). A two-phase hybrid algorithm for the capacitated location-routing problem. COR, 40(1), 70-79.
• Euchi, J., Chabchoub, H. and Yassine, A. (2011). New Evolutionary Algorithm Based On 2-Opt Local Search To Solve The Vehicle Routing Problem with Private fleet and common carrier. International Journal of Applied Metaheuristic, 2(1) 58-82.
• Figliozzi, M. (2010). Vehicle Routing Problem for Emissions Minimization. Transportation Research Record, 2197, 1-7.
• Fischetti, M., Toth P. and Vigo, D. (1994). A branch and bound algorithm for the capacitated vehicle routing problem on direct graphs. Operations Research, 42, 846-859.Fukasawa, R., Lysgaard, J., de Aragão, M. P., Reis, M., Uchoa, E. and Werneck, R. F. (2004). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Lecture Notes in Computer Science, 3064, 1-15.
• García-Nájera, A. (2012). The vehicle routing problem with backhauls: a multi-objective evolutionary approach. In Hao, J.-K. and Middendorf, M. (Eds.), Evolutionary Computation in Combinatorial Optimization. Lecture Notes in Computer Science, 7245, 255-266. Springer.
• Gendreau, M., Hertz, A. and Laporte, G. (2001). New insertion and post-optimization procedures for TSP. OR, 40, 1086-1094.
• Ghannadpour, S. F., Noori, S., T.-Moghaddam R. and Ghoseiri, K. (2014). A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application. Applied Soft Computing, 14, Part C, 504-527.
• Ghiani, G., Guerriero, F., Laporte, G. and Musmanno, R. (2003). Real-Time Vehicle Routing: Solution Concepts, Algorithms And Parallel Computing Strategies. EJOR, 151(1), 1-11.
• Ghiani, G. and Improta, G. (2000). An Efficient Transformation Of The Generalized Vehicle Routing Problem. EJOR, 122(1), 11-17.
• Giagli, G., Minis, I., Tatarakis, A. and Zeimpekis, V. (2004). Minimizing Logistics Risk Through RTVRP And Mobile Technologies: Research. IJPD & LM, 34(9), 749-764.
• Golden, B., Magnanti, L. and Nguyan, H. (1972). Implementing Vehicle Routing Algorithms. Networks, 7(2), 113-148.
• Golden, B. and Stewart, W. (1975). Vehicle Routing Problem with Probabilistic Demands. Computer Sciencie and statistics: tenth annual symposium on the interface, 503, 252-259.
• Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126, 106-130.
• Hemmelmayr, V. and Doerner, K. (2009). A variable neighboorhood search heuristic for periodical vehicle routing problems. EJOR, 195(3), 791-802.
• Hutton, B. (2002). The importance of relating fuel consumption rates and driving cycles, measuring, modelling, monitoring and motivation changes in fuel consumption. Transport Research Institute Workshop.
• Jaramillo, J. R. (2011). The green vehicle routing procedure. In Proceedings, informs annual meeting, October 5-7, Myrtle Beach, South Carolina, USA.
• Jemai, J., Zekri, M. and Mellouli, K. (2012). An NSGA-II Algorithm for the Green Vehicle Routing Problem. 12th European Conference. Málaga, Spain. Springer Berlin Heidelberg, 37-48.
• Jorgensen, M. and Larsen, J. (2006). Solving Dial-a ride problem using Genetic Algorithm. JOR Society, 58, 1321-1331.
• Kara, I. (2010). On the Miller-Tucker-Zemlin Based Formulations for the Distance-Constrained Capacitated Vehicle Routing Problem. AIP Conference Proceedings, 1309, 551-561.
• Kara, I. (2011). Arc Based Integer Programming Formulations For Distance-Constrained Capacitated Vehicle Routing Problem. LINDI. 3rd IEEE International Symposium on IEEE.
• Kara, I. and Bektas, T. (2003). Integer Linear Problem Formulation Of The Generalized Vehicle Routing Problem. In Proc. 5-th EURO/inf. JIM,2003.
• Kara, I. and Pop, C. ( 2008). New Mathematical Models of the Generalized Vehicle Routing Problems and extensionsInt. Conf. on Applied Mahematical Programming and Modelling, Bratislava, Slovakia.
• Koskosidis, Y., Powell, W. and Solomon, M. (1982). An optimization-based heuristic for vehicle routing and scheduling problem with soft time windows constraints. Transportation Sciencie, 26(2), 69-85.
• Kucukoglu, I., Ene, S., Askoy, A. and Ozturk, N. (2013). A green capacitated vehicle routing problem with fuel consumption optimization model. International Journal of Computational Engineering Research, 3(7), 16-23.
• Kumar, S. and Pannerselvam, R. (2012). A survey on the Vehicle Routing Problem and its variants. Intelligent Information Management, 4, 66-74.
• Kuo, Y. (2011). Using simulated annealing to minimize fuel consumption for the time dependent vehicle routing problem. Computers & Industrial Enginnering, 131, 44-51.
• Kwon, Y., Choi, Y. and Lee, D. (2013). Heterogeneous fixed fleet vehicle routing considering carbon emission. Transportation Research Part D, 23, 81-89.
• Labbé, M., Laporte, G. and Mercure, H. (1991). Capacitated Vehicle Routing Problems on trees. OR, 39, 616-622.
• Lacomme, P., Prins, C. and Ramdane, W. (2001). A Genetic Algorithm for the Capacitated arc routing problem and its extensions. In AEC, E.J.W. Boers (Ed.), Lecture Notes in Computer Sciencies, 2037, 473-483. Springer.
• Laporte, G. (1992). The VRP: An Overview Of Exact And Approximate algorithms. EJOR, 59, 345-358.
• Laporte, G., Gendreau, M., Potvin, J. and Semet, F. (2002). Classical and modern heuristics for the vehicle routing problem. International Transactions in OR, 7, 285-300.
• Laporte, G. and Nobert, Y. (1987). Exact algorithms for the Vehicle Routing Problem. Discrete Mathematics, 31, 147-184.
• Lau, C. H. Sim, M. and Teo M. K. (2003). Vehicle routing problem with time windows and limited number of vehicles. European Journal of Operational Research, 148, 3,559-569
• Leal, I. and D’Agosto, M. (2011). Choice For Transportation Of Hazardous Materials: The Case Of Land Modes Of Transport Of Bio-Ethanol In Brazil. Journal of Cleaner Production, 19(2-3), 229-240.
• Levin, A. (1971). Scheduling And Fleet Routing Models For Transportation Systems. Transportation Sciencie, 5(3), 232-256.
• Li, F., Golden, B. and Wasil, E. (2007). The open vehicle routing problem : algorithms large-scale test problem, and computational results. Computers & Operations Research, 34, 2918-2930.
• Li, X., Leung, S.C.H. and Tian, P. (2012). A multistart adaptative memory based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem. Experts Systems with Application, 39, 365-374.
• Liebman, J. and Marks, D. (1970). Mathematical analysis of solid waste collections. Public Health Service. Publ No 2065. Ms Depot of Health. Education and Welfare.
• Lima, C., Goldbarg, M. and Goldbarg, E. (2004). A Memetic Algorithm for the HFVRP. Electronic Notes in Discrete Math, 18, 171-176.
• Liong, Ch-.Y., Wan Rosmanira, I., Khairuddin, O. and Zirour, M. (2008). Vehicle Routing Problem: Models And Solutions. JQMA, 4 (1), 205-218.
• Malandraki, C. and Daskin, M. (1992). Time Dependent Vehicle Routin Problem: Formulations, Solution Algorithms And Computational Experiments. Transportation Sciencie, 26(3), 185-200.
• Marinakis, Y., Migdalas, A. and Pardalos, P. (2007). A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm. J Glob Optim, 38, 555-580.
• Marks, H. and Stricker, R. (1971). Routing For Public Service Vehicles. ASCE Journal of the Urban Planning and Development Division, 97(UP2), 165-178.
• Martinelli, R., Pecin, D., Poggi, M. and Longo, H. (2010). Column generation bounds for Capacitated arc routing problem. In Proceedings of the XLII SOBRAPO.
• Martinelli, R., Poggi, M. and Subramanian, A. (2011). Improved bounds for large scale capacitated arc routing problem. Technical report MCC14/11, Dep. de Informática, (PUC-Rio), Brazil.
• Mbaraga, P., Langevin, A. and Laporte, G. (1999). Two exact algorithms for the vehicle routing problem on trees. Naval Research Logistics, 46, 75-89.
• McKinnon, A. and Woodburn, A. (1996). Logistical Restructuring And Road Freight Traffic Growth: An Empirical Assessment. Transportation, 23(2), 141-161.Bhawna Minocha et al / (IJCSIT) International Journal of Computer Science and Information Technologies, Vol. 2 (6) , 2011, 2671-2676.
• Minocha, B.; Tripathi, S.; Mohan, C., Solving. (2011). Vehicle Routing and scheduling problems using hybrid genetic algorithm.  Electronics Computer Technology (ICECT), 2011 3rd International Conference on , vol.2,   189-193.
• Mole, R. and S. Jameson, S. (1976). A sequential route-building algorithm employingageneralized saving criterion. Operation Research Quarterly, 11, 503-511.
• Nagy, G. and Salhi, S. (2003). Heuristic algorithms for single and multiple depot vehicle routing problems with pick ups and deliveries. Working Paper no. 42, Canterbury Business School.
• Naud, M. and Potvin, J. (2009). Tabu Search with ejections chains for Vehicle Routing Problem with Private Fleet and Common Carrier. CIRRELT-2009-50.
• Olivera, A. and Viera, O. (2007). Adaptive memory programming for the Vehicle routing problem with multiple trips. COR, 34(1), 28-47.
• Ombuki-Berman, B. and Hanshar, F. (2009). Using GA for multi-depot vehicle routing. In Bio-Inspired Algorithms for the VRP (161, 77-99). Ed: Springer - Studies in Computational Int.
• Özyurt, Z., Aksen, D. and Aras, N. (2006). OVRP with time deadlines: solution methods and applications. OR Proceedings 2005. Springer Berlin Heidelberg, 73-78.
• Palmer, A. (2008). The Development of an Integrated Routing and Carbon Dioxide Emissions Model for Goods Vehicles. PhD Thesis. Cranfield University.
• Paraskevopoulos, D., Repoussis, P., Tarantilis, C., Ioannou, G. and Prastacos, G. (2008). A Reactive VNSTS For The HFVRP With Time Windows. Journal of Heuristics, 14(5), 425-455.
• Perboli, G. and Tadei, R. (2010). New Families Of Valid Inequalities For The Two-Echelon Vehicle Routing Problem. Electronic Notes in Discrete Mathematics, 36, 639-646.
• Pessoa, A., Uchoa, E. and de Aragão, P. (2008). The VRP: Latest advances and New Challenges. Robust Branch-Cut-Price Algorithms for VRP. Springer, 297-325.
• Piecyk, M. (2010). Analysis Of Long-Term Freight Transport, Logistics And Related CO2 Trendson A Business-As-Usual Basis. Doctor of Philosophy, Heriot-Watt University.
• Pop, P., Pintea, C. and Zelina, I. (2008). Solving The Generalized Vehicle Routing Problem with an ACS-based Algorithm. AIP Conference Proceedings: BICS,1117(1), 157-162.
• Pradenas, L., Oportus, B. and Parada, V. (2013). Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling. ES with Applications, 40(8), 2985-2991.
• Prins, C., Prodhon, C., Ruiz, A., Soriano, P. and Wolfler, R. (2007). Solving the CLRP by a Coop. Lagrangean Relaxation-Granular Heuristic. Transportation Sciencie, 41(4), 470-483.
• Qiu, L., Hsu, W., Huang, S. and Wangz, H. (2002). Scheduling and routing algorithms for AGVs: a Survey. International Journal Production Research, 40(3), 745,760.
• Quariguasi, F., Walther, G., Bloemho, J., Nunnen, J. and Spengler, T. (2009). A Methodology for assesing eco-efficiency in logistics networks. European Journal Operations Research, 193, 670-682.
• Reisman, A. (1992). Management Science Knowledge: Its Creation, Generalization, and Consolidation. Greenwood P.
• Renaud, J., Laporte, G. and Boctor, F. (1996). A Tabu Search heuristic for the Multi Depot Vehicle Routing Problem. COR, 23, 229-235.
• Romilly, P. (1999). Substitution of bus for car travel in urban britain: an economic evaluation of bus and car exhaust emission and other costs. Transportation Research part D: Transport and Enviroment, 4(2), 109-125.
• Salhi, S. and Sari, M. (1997). A multi-level composite heuristic for the multidepot vehicle fleet mix problem. EJOR, 103, 95-112.
• Sariklis, D. and Powell, S. (2000). A Heuristic Method The Open Vehicle Routing Problem. JORS, 51, 564-573.
• Sarkis, J., Zhu, Q. and Lai, K. (2011). An organizational theoretic review of green supply chain management literature. International Journal of Production Economics, 130, 1-15.
• Sbihi, A. and Eglease, W. (2007). The relationship between VRP and Scheduling and Green Logistics - A Literature Survey.Working paper. The Department of Management Science Lancaster University Management School, UK.
• Shen, Z., Ordóñez, F. and Dessouky, M. M. (2009). The stochastic vehicle routing problem for minimum unmet demand; chap. IV. Springer Optimization and Its Applications. Springer US, Boston, MA, 349-37.
• Solomon, M. (1987). Algorithms For Vehicle Scheduling Routing Problem With Time Windows. Operations Research, 35(2), 354-265.
• Srivastava, S. (2007). Green Supply-Chain Managment. A State Of The Art Literature Review. International Journal of Managment Reviews, 9(1), 53-80.
• Subramanian, A. (2012). Heuristic, exact and hybrid approaches for VRP. PhD Thesis. Universidade Federal Fluminense. Niteroi.
• Subramanian, A., Drummon, L., Bentes, C., Ochu, L. S. and Farias, R. (2010). A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research, 37(11), 1899-1911.
• Suzuki, Y. (2011). A new truck-routing approach for reducing fuel consumption and pollutants emission. Transportation Research Part D: Transport and E, 16(1), 73-77.
• Thangiah, S. Vinayagamoorty, R. and Gubbi A. (1993). Vehicle routing and time deadlines using genetic and loca algorithms. Proceedings of the 5th International Conference on Genetic Algorithms, 506-515
• Thompson, P. M. and Psaraftis, H. N. (1993). Cyclic transfer algorithms for multivehicle routing and scheduling problems. Oper. Res., 41, 935-946.
• Toth, P. and Vigo, D. (2002). Models, Relaxations And Exact Approaches For The Capacitated Arc Routing Problem. Discrete Applied Mathematics, 123(1-3), 487-512.
• Ubeda, S., Arcelus, F. and Faulin, J. (2011). Green Logistics at eroski. A acse study. International Journal on Production Economics, 131, 44-51.
• Vachon, S. and Klassen, R. (2008). Enviromental Managment And Manufacturing Performance: The Role Of Collaboration In The Supply Chain. International Journal Production Economics, 111(2), 299-315.
• Vidal, T., Crainic, T. G., Gendreau, M. and Prins, C. (2013). Heuristics for multi-attribute vehicle routing problems: a survey and synthesis. EJOR, 231(1), 1-21.
• Vidal, T., Crainic, T. G., Gendreau, M. and Prins, C. (2014). Implicit depot assigments and rotations in vehicle routing heuristics. European Journal of Operational Research, 237(1), 15-28.
• Vigo, D. (1996). Heuristic Algorithm For The Arc Capacitated Vehicle Routing Problem. EJOR, 89, 108-126.
• Villegas, J. G., Prins, C., Prodhon, C., Medaglia, A. L. and Velasco, N. (2010). GRASP/VND and multi-start evolutionary local search for the single TTVRP with satellite depots. Engineering Applications of Artificial Intelligence, 23(5), 780-794.
• Wade, A. and Salhi, S. (2003). Anant system algorithm for the mixed vehicle routing problem with backhauls. In Resende, M. G. C and de Sousa, J. P. (Eds.): Metaheuristics: Computer Decision-Making (Chapter 33, 699-719). Kluwer.
• Wilck IV, J. H. and Cavalier, T. M. (2012). Construction Heuristic for the Split Delivery. American Journal of Operations Research, 2, 153-162. http://dx.doi.org/10.4236/ajor.2012.22018
• Wilson, N., Sussman, J., Wang, H. and Higonnet, B. (1971). Scheduling algorithms for dial-a-ride Systems. Massachusetts Institute of Technology, Cambridge. Technical report USL TR-70-13.
• Wu, T.H., Low, Ch. and Bai, J.-W. (2002). Heuristic solutions to multi depot location vehicle routing problems. Computers & Operations Research, 29, 1393,1415.
• Xiao, Y., Zhao, Q., Kaku, I. and Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers and Operations Research, 39(7), 1419-1431.
• Yeun, C. L., Ismail W.R., Omar K., Zirour, M. (2008) Vehicle routing problem: models and solutions. Journal of Quality Measurement and Analysis. 4(1), 205-218.

1.  Toro E. MSc en Ingeniería Eléctrica. MSc en Investigación de Operaciones y Estadística. Docente Facultad de Ingeniería Industrial, Universidad Tecnológica de Pereira. Pereira, Colombia. This email address is being protected from spambots. You need JavaScript enabled to view it.

2.       Escobar A.Ph.D en Ingeniería. Docente programa de Tecnología Eléctrica, Universidad Tecnológica de Pereira. Pereira, Colombia. This email address is being protected from spambots. You need JavaScript enabled to view it.

3.       Granada M.Ph.D en Ingeniería. Docente programa de Ingeniería Eléctrica, Universidad Tecnológica de Pereira. Pereira, Colombia. This email address is being protected from spambots. You need JavaScript enabled to view it.

Para citar este artículo: Toro, E., Escobar A. y Granada, M. (2016). Literature review of vehicle routing problem in the green transportation context. Revista Luna Azul, 42, 362-387. Recuperado de http://200.21.104.25/lunazul/index.php?option=com_content&view=article&id=143

Este obra está bajo una Licencia de Creative Commons Reconocimiento CC BY