Optimisation Models and Algorithms for Scheduling Transportation

Zhang, Yefei (Andy)

Optimisation Models and Algorithms for Scheduling Transportation

Zhang, Yefei (Andy)

Permalink

Publication Type:: Thesis
Issue Date:: 2024

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download thesisAdobe PDF (2.34 MB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, Yefei (Andy)
dc.date.accessioned	2024-04-22T03:30:38Z
dc.date.available	2024-04-22T03:30:38Z
dc.date.issued	2024
dc.identifier.uri	http://hdl.handle.net/10453/178168
dc.description	University of Technology Sydney. Faculty of Science.	en_US.UTF-8
dc.description.abstract	The thesis presents an optimisation framework called the Lagrangian ILS which aims at efficiently solving the practical vehicle routing problems (VRPs). This optimisation framework adaptively adjusts the weights of the coefficients in the iterated local search (ILS) metaheuristic using the Lagrangian relaxation technique. Three VRPs are studied in this thesis. For each problem, a problem-specific optimisation procedure is derived under the Lagrangian ILS framework. The first problem studied in this thesis is the Workforce Scheduling and Routing Problem. The Lagrangian ILS has been tested on a standard benchmark on this topic. The results have shown the superior performance of Lagrangian ILS in comparison with the state-of-the-art algorithm for this problem. The effectiveness of utilising the Lagrangian ILS is particularly noticeable in large instances, even when the Lagrangian ILS uses only half of the permissible number of iterations. After observing the great potential of the Lagrangian ILS, it is applied to a Simultaneous Pickup and Delivery Problem (SPDP) suggested by an Australian transportation company. The problem has ordered objectives. The primary objective is to maximise the number of served customers and the secondary objective is to minimise the total travel time. The thesis formulates the problem into a mixed integer program and solves the problem with a new optimisation procedure called ILS2O. The performance of the ILS2O is evaluated on three sets of benchmarks. One comprises real-world instances provided by the industry partner and the other two are derived from a standard benchmark for VRPs. The results have demonstrated that the ILS2O produces solutions with high quality and high consistency within the time frame imposed by the industry partner. The last problem studied is a Simultaneous Pickup and Delivery Problem with Preloading under Uncertainty (SPDPP) which is also motivated by an Australian transportation company. In this problem, customers are revealed in two stages. The assignment of customers in the first stage is called preloading. Since preloading is determined without knowing customers in the second stage, this problem is a stochastic vehicle routing problem. The thesis formulates the SPDPP as a 2-stage stochastic program and solves it using the Sample Average Approximation (SAA) approach. An optimisation procedure called ILS-SAA is proposed to accommodate the non-anticipativity constraints. The performance of ILS-SAA is tested on instances derived from historical data provided by the industry partner. Results of the computational experiments indicate that ILS-SAA yields favourable solutions within a reasonable time frame.	en_US.UTF-8
dc.format	Thesis (PhD)
dc.language.iso	en_US	en_US.UTF-8
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/178168/1/thesis.pdf
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	© 2024 Yefei Zhang
dc.rights	au.edu.uts.lib/cph
dc.title	Optimisation Models and Algorithms for Scheduling Transportation	en_US.UTF-8
dc.type	Thesis
utslib.copyright.status	open_access	*

Abstract:

The thesis presents an optimisation framework called the Lagrangian ILS which aims at efficiently solving the practical vehicle routing problems (VRPs). This optimisation framework adaptively adjusts the weights of the coefficients in the iterated local search (ILS) metaheuristic using the Lagrangian relaxation technique. Three VRPs are studied in this thesis. For each problem, a problem-specific optimisation procedure is derived under the Lagrangian ILS framework. The first problem studied in this thesis is the Workforce Scheduling and Routing Problem. The Lagrangian ILS has been tested on a standard benchmark on this topic. The results have shown the superior performance of Lagrangian ILS in comparison with the state-of-the-art algorithm for this problem. The effectiveness of utilising the Lagrangian ILS is particularly noticeable in large instances, even when the Lagrangian ILS uses only half of the permissible number of iterations. After observing the great potential of the Lagrangian ILS, it is applied to a Simultaneous Pickup and Delivery Problem (SPDP) suggested by an Australian transportation company. The problem has ordered objectives. The primary objective is to maximise the number of served customers and the secondary objective is to minimise the total travel time. The thesis formulates the problem into a mixed integer program and solves the problem with a new optimisation procedure called ILS2O. The performance of the ILS2O is evaluated on three sets of benchmarks. One comprises real-world instances provided by the industry partner and the other two are derived from a standard benchmark for VRPs. The results have demonstrated that the ILS2O produces solutions with high quality and high consistency within the time frame imposed by the industry partner. The last problem studied is a Simultaneous Pickup and Delivery Problem with Preloading under Uncertainty (SPDPP) which is also motivated by an Australian transportation company. In this problem, customers are revealed in two stages. The assignment of customers in the first stage is called preloading. Since preloading is determined without knowing customers in the second stage, this problem is a stochastic vehicle routing problem. The thesis formulates the SPDPP as a 2-stage stochastic program and solves it using the Sample Average Approximation (SAA) approach. An optimisation procedure called ILS-SAA is proposed to accommodate the non-anticipativity constraints. The performance of ILS-SAA is tested on instances derived from historical data provided by the industry partner. Results of the computational experiments indicate that ILS-SAA yields favourable solutions within a reasonable time frame.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/178168