Leveraging Machine Learning Methods to Solve Electric Vehicle Routing Problem Variants

In recent years, machine learning techniques and technologies have spurred a revolution in our ability to solve an array of difficult problems. Now, another major revolution is beginning: machine learning methods are being used to solve ever more sophisticated and difficult decision and optimisation problems to an ever greater degree of success. A variety of techniques have emerged to leverage data alongside limited domain knowledge to replace extensive human engineering of solution methods. These techniques are in their infancy, however, and a race is underway to establish which of them are viable for a range of optimisation problems. In this thesis, a focus is placed on two of these learning-based techniques: learning-to-prune and end-to-end learning. We use these approaches to solve a particularly important and difficult family of optimisation problems, the vehicle routing problems. Learning-to-prune techniques aim to restrict the effective size of the solution space of an optimisation problem or decision problem, potentially significantly reducing the computational effort required to solve them for a small sacrifice in the ultimate solution quality. We extend the learning-to-prune approach, which has been shown in the literature to be capable of identifying new best-known solutions, to the vehicle routing problem and its variants. We develop a new framework, using pseudolabels, that does not rely on the ability to collect a large dataset of optimal solutions, which is not possible for many highly-constrained routing problems. We show that this approach, similar to weak supervision, can be more effective than the traditional learning-to-prune approaches and can be used to solve larger problem instances than would otherwise be possible. This approach is used to solve large problem instances of the travelling salesman problem and instances of the electric vehicle routing problem with nonlinear and partial charging. We identify a number of conditions that must be met to make these approaches effective for routing problems and identify additional, future research directions that may yield improved results The end-to-end learning techniques, which have been traditionally successful at solving a limited set of
problem instances, have been shown in previous works to have promise for the class of routing problems. They can produce high-quality solutions with limited computational effort and could, in theory, be easily modified to solve many different variants of routing problem. In this thesis we show that end-to-end learning models can be used to solve a wide range of problem instances and can be modified to do so in a scalable and generalisable manner. These models can be used to solve problems with tens to thousands of customers, obtaining high-quality solutions. This thesis presents the first application of these models for solving green vehicle routing problems. This significantly increases the prospect of these approaches being suitable for solving more sophisticated, difficult and highly-constrained routing problems, which may occur in the real world. We show in this thesis that conceptual simplicity of these approaches and the potential that they have to augment existing solution techniques makes them attractive for future integration to existing approaches and further development.