Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 16 of 16
Full-Text Articles in Physical Sciences and Mathematics
Conditional Neural Heuristic For Multiobjective Vehicle Routing Problems, Mingfeng Fan, Yaoxin Wu, Zhiguang Cao, Wen Song, Guillaume Sartoretti, Huan Liu, Guohua Wu
Conditional Neural Heuristic For Multiobjective Vehicle Routing Problems, Mingfeng Fan, Yaoxin Wu, Zhiguang Cao, Wen Song, Guillaume Sartoretti, Huan Liu, Guohua Wu
Research Collection School Of Computing and Information Systems
Existing neural heuristics for multiobjective vehicle routing problems (MOVRPs) are primarily conditioned on instance context, which failed to appropriately exploit preference and problem size, thus holding back the performance. To thoroughly unleash the potential, we propose a novel conditional neural heuristic (CNH) that fully leverages the instance context, preference, and size with an encoder–decoder structured policy network. Particularly, in our CNH, we design a dual-attention-based encoder to relate preferences and instance contexts, so as to better capture their joint effect on approximating the exact Pareto front (PF). We also design a size-aware decoder based on the sinusoidal encoding to explicitly …
Multi-View Graph Contrastive Learning For Solving Vehicle Routing Problems, Yuan Jiang, Zhiguang Cao, Yaoxin Wu, Jie Zhang
Multi-View Graph Contrastive Learning For Solving Vehicle Routing Problems, Yuan Jiang, Zhiguang Cao, Yaoxin Wu, Jie Zhang
Research Collection School Of Computing and Information Systems
Recently, neural heuristics based on deep learning have reported encouraging results for solving vehicle routing problems (VRPs), especially on independent and identically distributed (i.i.d.) instances, e.g. uniform. However, in the presence of a distribution shift for the testing instances, their performance becomes considerably inferior. In this paper, we propose a multi-view graph contrastive learning (MVGCL) approach to enhance the generalization across different distributions, which exploits a graph pattern learner in a self-supervised fashion to facilitate a neural heuristic equipped with an active search scheme. Specifically, our MVGCL first leverages graph contrastive learning to extract transferable patterns from VRP graphs to …
A Review On Learning To Solve Combinatorial Optimisation Problems In Manufacturing, Cong Zhang, Yaoxin Wu, Yining Ma, Wen Song, Zhang Le, Zhiguang Cao, Jie Zhang
A Review On Learning To Solve Combinatorial Optimisation Problems In Manufacturing, Cong Zhang, Yaoxin Wu, Yining Ma, Wen Song, Zhang Le, Zhiguang Cao, Jie Zhang
Research Collection School Of Computing and Information Systems
An efficient manufacturing system is key to maintaining a healthy economy today. With the rapid development of science and technology and the progress of human society, the modern manufacturing system is becoming increasingly complex, posing new challenges to both academia and industry. Ever since the beginning of industrialisation, leaps in manufacturing technology have always accompanied technological breakthroughs from other fields, for example, mechanics, physics, and computational science. Recently, machine learning (ML) technology, one of the crucial subjects of artificial intelligence, has made remarkable progress in many areas. This study thoroughly reviews how ML, specifically deep (reinforcement) learning, motivates new ideas …
Learning Large Neighborhood Search For Vehicle Routing In Airport Ground Handling, Jianan Zhou, Yaoxin Wu, Zhiguang Cao, Wen Song, Jie Zhang, Zhenghua Chen
Learning Large Neighborhood Search For Vehicle Routing In Airport Ground Handling, Jianan Zhou, Yaoxin Wu, Zhiguang Cao, Wen Song, Jie Zhang, Zhenghua Chen
Research Collection School Of Computing and Information Systems
Dispatching vehicle fleets to serve flights is a key task in airport ground handling (AGH). Due to the notable growth of flights, it is challenging to simultaneously schedule multiple types of operations (services) for a large number of flights, where each type of operation is performed by one specific vehicle fleet. To tackle this issue, we first represent the operation scheduling as a complex vehicle routing problem and formulate it as a mixed integer linear programming (MILP) model. Then given the graph representation of the MILP model, we propose a learning assisted large neighborhood search (LNS) method using data generated …
Learning Generalizable Models For Vehicle Routing Problems Via Knowledge Distillation, Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, Yeow Meng Chee
Learning Generalizable Models For Vehicle Routing Problems Via Knowledge Distillation, Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, Yeow Meng Chee
Research Collection School Of Computing and Information Systems
Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring the knowledge distillation to this field and propose an Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme for learning more generalizable deep models. Particularly, our AMDKD leverages various knowledge from multiple teachers trained on exemplar distributions to yield a light-weight yet generalist student model. Meanwhile, we equip AMDKD with an adaptive strategy that allows the student to concentrate on difficult distributions, so as to absorb hard-to-master knowledge more effectively. Extensive experimental results …
Learning Improvement Heuristics For Solving Routing Problems, Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, Andrew Lim
Learning Improvement Heuristics For Solving Routing Problems, Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, Andrew Lim
Research Collection School Of Computing and Information Systems
Recent studies in using deep learning to solve routing problems focus on construction heuristics, the solutions of which are still far from optimality. Improvement heuristics have great potential to narrow this gap by iteratively refining a solution. However, classic improvement heuristics are all guided by hand-crafted rules which may limit their performance. In this paper, we propose a deep reinforcement learning framework to learn the improvement heuristics for routing problems. We design a self-attention based deep architecture as the policy network to guide the selection of next solution. We apply our method to two important routing problems, i.e. travelling salesman …
Enhancing A Qubo Solver Via Data Driven Multi-Start And Its Application To Vehicle Routing Problem, Whei Yeap Suen, Matthieu Parizy, Hoong Chuin Lau
Enhancing A Qubo Solver Via Data Driven Multi-Start And Its Application To Vehicle Routing Problem, Whei Yeap Suen, Matthieu Parizy, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
Quadratic unconstrained binary optimization (QUBO) models have garnered growing interests as a strong alternative modelling framework for solving combinatorial optimization problems. A wide variety of optimization problems that are usually studied using conventional Operations Research approaches can be formulated as QUBO problems. However, QUBO solvers do not guarantee optimality when solving optimization problems. Instead, obtaining high quality solutions using QUBO solvers entails tuning of multiple parameters. Here in our work, we conjecture that the initial states adjustment method used in QUBO solvers can be improved, where careful tuning will yield overall better results. We propose a data-driven multi-start algorithm that …
Neurolkh: Combining Deep Learning Model With Lin-Kernighan-Helsgaun Heuristic For Solving The Traveling Salesman Problem, Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
Neurolkh: Combining Deep Learning Model With Lin-Kernighan-Helsgaun Heuristic For Solving The Traveling Salesman Problem, Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
Research Collection School Of Computing and Information Systems
We present NeuroLKH, a novel algorithm that combines deep learning with the strong traditional heuristic Lin-Kernighan-Helsgaun (LKH) for solving Traveling Salesman Problem. Specifically, we train a Sparse Graph Network (SGN) with supervised learning for edge scores and unsupervised learning for node penalties, both of which are critical for improving the performance of LKH. Based on the output of SGN, NeuroLKH creates the edge candidate set and transforms edge distances to guide the searching process of LKH. Extensive experiments firmly demonstrate that, by training one model on a wide range of problem sizes, NeuroLKH significantly outperforms LKH and generalizes well to …
Improving The Performance Of Transportation Networks: A Semi-Centralized Pricing Approach, Zhiguang Cao, Hongliang Guo, Wen Song, Kaizhou Gao, Liujiang Kang, Xuexi Zhang, Qilun Wu
Improving The Performance Of Transportation Networks: A Semi-Centralized Pricing Approach, Zhiguang Cao, Hongliang Guo, Wen Song, Kaizhou Gao, Liujiang Kang, Xuexi Zhang, Qilun Wu
Research Collection School Of Computing and Information Systems
Improving the performance of transportation network is a crucial task in traffic management. In this paper, we start with a cooperative routing problem, which aims to minimize the chance of road network breakdown. To address this problem, we propose a subgradient method, which can be naturally implemented as a semi-centralized pricing approach. Particularly, each road link adopts the pricing scheme to calculate and adjust the local toll regularly, while the vehicles update their routes to minimize the toll costs by exploiting the global toll information. To prevent the potential oscillation brought by the subgradient method, we introduce a heavy-ball method …
Vehicle Routing: Review Of Benchmark Datasets, Aldy Gunawan, Graham Kendall, Barry Mccollum, Hsin-Vonn Seow, Lai Soon Lee
Vehicle Routing: Review Of Benchmark Datasets, Aldy Gunawan, Graham Kendall, Barry Mccollum, Hsin-Vonn Seow, Lai Soon Lee
Research Collection School Of Computing and Information Systems
The Vehicle Routing Problem (VRP) was formally presented to the scientific literature in 1959 by Dantzig and Ramser (DOI:10.1287/mnsc.6.1.80). Sixty years on, the problem is still heavily researched, with hundreds of papers having been published addressing this problem and the many variants that now exist. Many datasets have been proposed to enable researchers to compare their algorithms using the same problem instances where either the best known solution is known or, in some cases, the optimal solution is known. In this survey paper, we provide a list of Vehicle Routing Problem datasets, categorized to enable researchers to have easy access …
Deep Reinforcement Learning Approach To Solve Dynamic Vehicle Routing Problem With Stochastic Customers, Waldy Joe, Hoong Chuin Lau
Deep Reinforcement Learning Approach To Solve Dynamic Vehicle Routing Problem With Stochastic Customers, Waldy Joe, Hoong Chuin Lau
Research Collection School Of Computing and Information Systems
In real-world urban logistics operations, changes to the routes and tasks occur in response to dynamic events. To ensure customers’ demands are met, planners need to make these changes quickly (sometimes instantaneously). This paper proposes the formulation of a dynamic vehicle routing problem with time windows and both known and stochastic customers as a route-based Markov Decision Process. We propose a solution approach that combines Deep Reinforcement Learning (specifically neural networks-based TemporalDifference learning with experience replay) to approximate the value function and a routing heuristic based on Simulated Annealing, called DRLSA. Our approach enables optimized re-routing decision to be generated …
Goods Consumed During Transit In Split Delivery Vehicle Routing Problems: Modeling And Solution, Wenzhe Yang, Di Wang, Wei Pang, Ah-Hwee Tan, You Zhou
Goods Consumed During Transit In Split Delivery Vehicle Routing Problems: Modeling And Solution, Wenzhe Yang, Di Wang, Wei Pang, Ah-Hwee Tan, You Zhou
Research Collection School Of Computing and Information Systems
This article presents the modeling and solution of an extended type of split delivery vehicle routing problem (SDVRP). In SDVRP, the demands of customers need to be met by efficiently routing a given number of capacitated vehicles, wherein each customer may be served multiple times by more than one vehicle. Furthermore, in many real-world scenarios, consumption of vehicles en route is the same as the goods being delivered to customers, such as food, water and fuel in rescue or replenishment missions in harsh environments. Moreover, the consumption may also be in virtual forms, such as time spent in constrained tasks. …
Using Reinforcement Learning To Minimize The Probability Of Delay Occurrence In Transportation, Zhiguang Cao, Hongliang Guo, Wen Song, Kaizhou Gao, Zhengghua Chen, Le Zhang, Xuexi Zhang
Using Reinforcement Learning To Minimize The Probability Of Delay Occurrence In Transportation, Zhiguang Cao, Hongliang Guo, Wen Song, Kaizhou Gao, Zhengghua Chen, Le Zhang, Xuexi Zhang
Research Collection School Of Computing and Information Systems
Reducing traffic delay is of crucial importance for the development of sustainable transportation systems, which is a challenging task in the studies of stochastic shortest path (SSP) problem. Existing methods based on the probability tail model to solve the SSP problem, seek for the path that minimizes the probability of delay occurrence, which is equal to maximizing the probability of reaching the destination before a deadline (i.e., arriving on time). However, they suffer from low accuracy or high computational cost. Therefore, we design a novel and practical Q-learning approach where the converged Q-values have the practical meaning as the actual …
A Mathematical Programming Model For The Green Mixed Fleet Vehicle Routing Problem With Realistic Energy Consumption And Partial Recharges, Vincent F. Yu, Panca Jodiwan, Aldy Gunawan, Audrey Tedja Widjaja
A Mathematical Programming Model For The Green Mixed Fleet Vehicle Routing Problem With Realistic Energy Consumption And Partial Recharges, Vincent F. Yu, Panca Jodiwan, Aldy Gunawan, Audrey Tedja Widjaja
Research Collection School Of Computing and Information Systems
A green mixed fleet vehicle routing with realistic energy consumption and partial recharges problem (GMFVRP-REC-PR) is addressed in this paper. This problem involves a fixed number of electric vehicles and internal combustion vehicles to serve a set of customers. The realistic energy consumption which depends on several variables is utilized to calculate the electricity consumption of an electric vehicle and fuel consumption of an internal combustion vehicle. Partial recharging policy is included into the problem to represent the real life scenario. The objective of this problem is to minimize the total travelled distance and the total emission produced by internal …
Approximating The Performance Of A "Last Mile" Transportation System, Hai Wang, Amedeo Odoni
Approximating The Performance Of A "Last Mile" Transportation System, Hai Wang, Amedeo Odoni
Research Collection School Of Computing and Information Systems
The Last Mile Problem (LMP) refers to the provision of travel service from the nearest public transportation node to a home or office. We study the supply side of this problem in a stochastic setting, with batch demands resulting from the arrival of groups of passengers who request last-mile service at urban rail stations or bus stops. Closedform approximations are derived for the performance of Last Mile Transportations Systems as a function of the fundamental design parameters of such systems. An initial set of results is obtained for the case in which a fleet of vehicles of unit capacity provides …
Real-Life Vehicle Routing With Non-Standard Constraints, Wee Leong Lee
Real-Life Vehicle Routing With Non-Standard Constraints, Wee Leong Lee
Research Collection School Of Computing and Information Systems
Real-life vehicle routing problems comprise of a number of complexities that are not considered by the classical models found in vehicle routing literature. I present, in this paper, a two-stage sweep-based heuristic to find good solutions to a real-life Vehicle Routing Problem (VRP). The problem I shall consider, will deal with some non-standard constraints beyond those normally associated with the classical VRP. Other than considering the capacity constraints for vehicles and the time windows for deliveries, I shall introduce four additional non-standard constraints: merging of customer orders, controlling the maximum number of drop points, matching orders to vehicle types, and …