A bi-objective mathematical model for a simultaneous pickup and delivery green vehicle routing problem with backhauls and time windows

Date of Publication

2014

Document Type

Master's Thesis

Degree Name

Master of Science in Industrial Engineering

College

Gokongwei College of Engineering

Department/Unit

Industrial and Systems Engineering

Thesis Adviser

Dennis Cruz

Defense Panel Chair

Bryan Gobaco

Defense Panel Member

Ronaldo Polancos
Eric Siy

Abstract/Summary

The Green Vehicle Routing Problem (GVRP), an extension of the Vehicle Routing Problem (VRP) that considers the environmental impact of freight transport operations, is considered as an effective way of improving the environmental performance of supply chain systems. This is because instead of only focusing on an economic objective, the GVRP also considers the environmental performance of the vehicle route.

This study has incorporated the concepts of GVRP into the Vehicle Routing Problem with Backhauls (VRPB). More specifically, this study has applied the GVRP into the Simultaneous Pickup and Delivery VRPB (SPD VRPB), a VRPB case wherein customers may be a linehaul customer, a backhaul customer, or both. This is a more advantageous approach as the SPD GVRPB is more flexible and efficient compared to the other VRPB cases, which are the Delivery-First Pickup Second VRPB and the Mixed VRPB.

The incorporation of the GVRP into the SPD VRPB to develop the Simultaneous Pickup and Delivery Green Vehicle Routing with Backhauls (SPD GVRPB) was performed through the development of a Mixed-Integer Nonlinear Program (MINLP) with two objective functions. The first objective is the minimization of the energy consumed by the vehicle in the route. This is the environmental objective of the model, as it is able to directly translate into the fuel consumption and GHG emissions of the vehicle. The second objective, on the other hand, is the time-based costs incurred in the system. This is the economic objective of the model, and pertains to the time-dependent costs that can be incurred in a vehicle routing operation.

Aside from using a bi-objective approach, another distinction of this study from previous GVRP researches is that the vehicle routing solution considers four key factors in a vehicle routing system: the distance travelled by the vehicle, the travel speed, the weight of the load carried, and the customer time windows. Each of these factors affect both objective functions and the aim of the MINLP model is to balance the trade-offs that exist among them.

Because the SPD GVRPB model is an NP-hard combinatorial optimization problem that is the first of its kind, no solution methodology exists to solve this. With that, this study has also adapted an Elitist Ant Colony Optimization technique in order to have a way of using the MINLP SPD GVRPB model. For computational efficiency, a computer program was developed for implementing the solution methodology.

The model and the solution methodology were validated using a test case scenario, and a sensitivity analysis was performed to understand the behavior of the model amid changing parameters. It was found out that a better performance in terms of both objectives can be achieved when the vehicle travels shorter distances and carried lesser loads. Furthermore, factors such as the altitude of customer locations, the distances between nodes, the travel speed, and the weight of the load carried, customer time windows, and penalty costs were all identified to affect the optimal routing solutions developed. The model aims to balance the tradeoffs between these factors in order to achieve the optimal routing solution.

A complexity analysis was also performed to determine if the Elitist Ant Colony algorithm performed better than an enumerative approach of computation and in order to understand the behavior of the model as the size of the problem increases. A summary of the study is also provided, with potential research direction for future studies.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTG005714

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

1 computer disc ; 4 3/4 in.

This document is currently not available here.

Share

COinS