Performance Comparison of Two Recent Heuristics for Green Time Dependent Vehicle Routing Problem

Performance Comparison of Two Recent Heuristics for Green Time Dependent Vehicle Routing Problem

Mehmet Soysal, Mustafa Çimen, Mine Ömürgönülşen, Sedat Belbağ
Copyright: © 2019 |Pages: 11
DOI: 10.4018/IJBAN.2019100101
(Individual Articles)
No Current Special Offers


This article concerns a green Time Dependent Capacitated Vehicle Routing Problem (TDCVRP) which is confronted in urban distribution planning. The problem is formulated as a Markovian Decision Process and a dynamic programming (DP) approach has been used for solving the problem. The article presents a performance comparison of two recent heuristics for the green TDCVRP that explicitly accounts for time dependent vehicle speeds and fuel consumption (emissions). These heuristics are the classical Restricted Dynamic Programming (RDP) algorithm, and the Simulation Based RDP that consists of weighted random sampling, RDP heuristic and simulation. The numerical experiments show that the Simulation Based Restricted Dynamic Programming heuristic can provide promising results within relatively short computational times compared to the classical Restricted Dynamic Programming for the green TDCVRP.
Article Preview


This paper concerns a Vehicle Routing Problem (VRP) that has a single depot and multiple customers. The depot owns capacitated vehicles to satisfy the demand of the customers. Some customers are located in urban areas, and therefore are subject to severe traffic congestion according to the time of the day. In literature, the defined problem is known as the Time Dependent Capacitated Vehicle Routing Problem (TDCVRP) in which the travel times between locations are not known in advance and therefore are not constant.

Another matter of concern related to urban logistics is the increasing awareness on sustainability. The concept of “sustainability” has gained a significant attention in Operations Management literature (see Corbett & Kleindorfer, 2003; Chen, 2015; Linton, Klassen & Jayaraman, 2007), service operations (see Wolf and Mujtaba, 2011) and transportation systems (see Jia, Cumbie, Sankar & Yu, 2014). Sustainability is generally defined as using resources to meet the needs of the present without compromising the ability of future generations to meet their own needs (WCED, 1987). The growing concern towards sustainability is not only due to the scarce resources and global warming, but also because of the legal requirements. The stakeholders of any organizations are also concerned with the economic, social and environmental performance of a business (Afrin, 2016). The need for environmental protection and increasing demands for natural resources are forcing companies to reconsider their business models (Wu & Pagell, 2011).

Sustainable development of logistics also calls for activities that lead to the highest economic and social gains while reducing the negative environmental losses (Abbasi & Nilson, 2016). The emergence of global supply chains and increased reliance on suppliers by brand manufacturers has increased the amount of transportation and logistics occurring within the consumer economy (Ugarte, Golden & Dooley, 2016). That represents one of the reasons of an increase in the total environmental footprint associated with these activities. In some consumer product supply chains, the greenhouse gas emissions due to transportation are between 5% and 15% of total emissions over the product life cycle (Doherty & Hoyle, 2009). In line with the aforementioned developments, the related literature indicates the need for green decision support models that consider transportation emissions for the Capacitated Vehicle Routing Problem with non-constant travel times (Bektaş & Laporte, 2011; Jabali, van Woensel & de Kok, 2012; Çimen & Soysal, 2017).

The TDCVRP that we address here accounts for environmental concerns, i.e., fuel consumption and emissions from transportation activities. This means that, in contrast with traditional attempts which ignore energy consumption of vehicles and respect only travelled distance, the green TDCVRP takes explicit fuel consumption and emissions into account.

Dynamic Programming (DP) approach has been used to formulate the green TDCVRP (Soysal & Çimen, 2016). This decision support model is capable of managing relevant key performance indicators of the number of vehicles used, total traveled distance, total energy use (emissions), total driving time, total fuel cost, total wage cost and total routing cost. However, exponential storage and computational time requirements of the DP algorithm due to the curse of dimensionality render DP infeasible in large-sized problems.

Complete Article List

Search this Journal:
Volume 10: 1 Issue (2023)
Volume 9: 6 Issues (2022): 4 Released, 2 Forthcoming
Volume 8: 4 Issues (2021)
Volume 7: 4 Issues (2020)
Volume 6: 4 Issues (2019)
Volume 5: 4 Issues (2018)
Volume 4: 4 Issues (2017)
Volume 3: 4 Issues (2016)
Volume 2: 4 Issues (2015)
Volume 1: 4 Issues (2014)
View Complete Journal Contents Listing