An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations. (September 2017)

• Record Type: Journal Article
• Authors: Androutsopoulos, Konstantinos N.; Zografos, Konstantinos G.
• Is Part Of: Transportation research. Volume 82(2017)
• Page Start: 180
• Page End: 209
• Publication Date: 2017-09
• Subjects: Routing in congested networks -- Distribution planning -- Network reduction -- Environment -- Bi-criterion vehicle routing; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2017.06.013
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: A novel vehicle routing model realistically incorporating cost and pollution criteria. A k-shortest path approach for copying with the problem's computational requirements. A generic two-stage solution framework for solving the proposed model. A label setting algorithm is used to transform VRP routes to non-dominated solutions. Abstract: The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.