Login | Register

Data and Simulation Models for Route Optimization in Vehicle Routing Problem


Data and Simulation Models for Route Optimization in Vehicle Routing Problem

Sharma, Monika (2018) Data and Simulation Models for Route Optimization in Vehicle Routing Problem. Masters thesis, Concordia University.

[thumbnail of Monika_MCompSci_Thesis.pdf]
Text (application/pdf)
Monika_MCompSci_Thesis.pdf - Accepted Version


The generalization of online commerce to a wide range of industries is transforming customer's practices by removing the requirement of visiting the physical stores. This has made it essential to develop a system to improve pickup/delivery of items ordered online, in particular, to avoid the extra costs associated with failed home pickup/deliveries. This thesis aims to contribute to the development of such a system by developing failure prediction data models and a prototype of a simulator leveraging these models to improve the planning of routes.
We use Random Forest classifier to build failure prediction models. Three data re-sampling strategies are used to address class imbalance issue as the proportion of the failed services is much less than that of the successful ones. To interpret classification results, we extract Association Rules where the antecedent is a set of service features and the consequent is a failed service status. To avoid the memory limitations often caused for large datasets, we design a two-step algorithm to first extract Association Rules on the failed services. Then the limited set of rules are obtained based on the frequencies of the antecedents in the complete dataset and in the dataset containing only failed services. The simulation model is developed using the SimGrid library. It simulates route generated by the optimization model, introduces random service failures and computes total traveled distance and time.
We obtain good prediction results on the real dataset (aggregated dataset). Our classifier reaches an average sensitivity of 0.7 and an average specificity of 0.7 for the 5 studied types of failure. Association Rules reassert the importance of confirmation calls to prevent failures due to customers not at home, show the importance of the time window size, slack time, and geographical location of the customer for the other failure types, and highlight the effect of the retailer company on several failure types. The simulation model is successfully validated using sample routes. To reduce the occurrence of service failures, our data models could be coupled with optimizers through simulation or used to define counter-measures to be taken by human dispatchers.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Sharma, Monika
Institution:Concordia University
Degree Name:M.A. Sc.
Program:Computer Science
Date:5 November 2018
Thesis Supervisor(s):Jaumard, Brigitte and Glatard, Tristan
ID Code:984677
Deposited By: Monika Sharma
Deposited On:27 Oct 2022 13:49
Last Modified:27 Oct 2022 13:49
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top