Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication
- Publication Type
Articles 1 - 7 of 7
Full-Text Articles in Physical Sciences and Mathematics
Glop: Learning Global Partition And Local Construction For Solving Large-Scale Routing Problems In Real-Time, Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, Fanzhang Li
Glop: Learning Global Partition And Local Construction For Solving Large-Scale Routing Problems In Real-Time, Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, Fanzhang Li
Research Collection School Of Computing and Information Systems
The recent end-to-end neural solvers have shown promise for small-scale routing problems but suffered from limited real-time scaling-up performance. This paper proposes GLOP (Global and Local Optimization Policies), a unified hierarchical framework that efficiently scales toward large-scale routing problems. GLOP partitions large routing problems into Travelling Salesman Problems (TSPs) and TSPs into Shortest Hamiltonian Path Problems. For the first time, we hybridize non-autoregressive neural heuristics for coarse-grained problem partitions and autoregressive neural heuristics for fine-grained route constructions, leveraging the scalability of the former and the meticulousness of the latter. Experimental results show that GLOP achieves competitive and state-of-the-art real-time performance …
Segac: Sample Efficient Generalized Actor Critic For The Stochastic On-Time Arrival Problem, Honglian Guo, Zhi He, Wenda Sheng, Zhiguang Cao, Yingjie Zhou, Weinan Gao
Segac: Sample Efficient Generalized Actor Critic For The Stochastic On-Time Arrival Problem, Honglian Guo, Zhi He, Wenda Sheng, Zhiguang Cao, Yingjie Zhou, Weinan Gao
Research Collection School Of Computing and Information Systems
This paper studies the problem in transportation networks and introduces a novel reinforcement learning-based algorithm, namely. Different from almost all canonical sota solutions, which are usually computationally expensive and lack generalizability to unforeseen destination nodes, segac offers the following appealing characteristics. segac updates the ego vehicle’s navigation policy in a sample efficient manner, reduces the variance of both value network and policy network during training, and is automatically adaptive to new destinations. Furthermore, the pre-trained segac policy network enables its real-time decision-making ability within seconds, outperforming state-of-the-art sota algorithms in simulations across various transportation networks. We also successfully deploy segac …
Step-Wise Deep Learning Models For Solving Routing Problems, Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
Step-Wise Deep Learning Models For Solving Routing Problems, Liang Xin, Wen Song, Zhiguang Cao, Jie Zhang
Research Collection School Of Computing and Information Systems
Routing problems are very important in intelligent transportation systems. Recently, a number of deep learning-based methods are proposed to automatically learn construction heuristics for solving routing problems. However, these methods do not completely follow Bellman's Principle of Optimality since the visited nodes during construction are still included in the following subtasks, resulting in suboptimal policies. In this article, we propose a novel step-wise scheme which explicitly removes the visited nodes in each node selection step. We apply this scheme to two representative deep models for routing problems, pointer network and transformer attention model (TAM), and significantly improve the performance of …
Application-Aware Cross-Layer Enrgy-Eficient Routing Scheme, Xu Fang, Hiyin Zhang, Wang Jing, Xu Ning, Zhijong Wang, Deng Min
Application-Aware Cross-Layer Enrgy-Eficient Routing Scheme, Xu Fang, Hiyin Zhang, Wang Jing, Xu Ning, Zhijong Wang, Deng Min
Journal of System Simulation
Abstract: An aplication- aware cross-layer energy-effcient routing scheme (ACER) was presented to minimize the effect of supplt of terminals in ad hoc network composed of smart mobile devices. Features of energy consumption were sensed by application aware energy model with the application monitor and the remaining energy monitor. Stability of network path was monitored by link stability monitoring module in Data link layer. As the scheme used the idea of cross-layer design, network topology information, application-aware information in application layer and link-stability were utilized synthetically to make routing deisions in network layer;Simulations were crried out on NS2 platform. The …
Research On Adaptive Routing Algorithm For Wireless Weak-Connection Network, Hua Xiang, Hongjuan Yao, Wang Hai, Wang Zhao, Jietao Zhang, Lili Shu
Research On Adaptive Routing Algorithm For Wireless Weak-Connection Network, Hua Xiang, Hongjuan Yao, Wang Hai, Wang Zhao, Jietao Zhang, Lili Shu
Journal of System Simulation
Abstract: The wireless weak-connected network has the characteristics of long delay, high dynamic topology, and unstable links. With the lack of continuity from the source end to the destination end of network connection, in order to solve the problem of communication difficulty, the intelligence and adaptability of Physarum polycephalum are introduced, and the adaptive wireless weak-connected network routing algorithm is proposed. A wireless weak-connected network model is build and the mathematical relationships of link capacity is deduced. The next-hop selection strategy and optimal routing strategy is designed to achieve the best-effort delivery of data in wireless weak-connected network environmrnt. Simulation …
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. …
Simulation Of Joint Power Control Routing Algorithm For Interference And Energy Consumption In Crahns, Zhufang Kuang, Zhigang Chen
Simulation Of Joint Power Control Routing Algorithm For Interference And Energy Consumption In Crahns, Zhufang Kuang, Zhigang Chen
Journal of System Simulation
Abstract: Problems of interference power to primary user by secondary userand the secondary user's running out of energy under underlay spectrum access model in cognitive radio ad hoc networks (CRAHNs) were investigated. Joint power control, routing and spectrum (channel) allocation algorithm (PRSA) based on particle swarm optimization were proposed. The goal of PRSA was to minimize interference power to primary user and prolong lifetime of CRAHNs. Particle encoding, particle initialization, fitness function, particle flight were included in PRSA. An Adjacency matrix with two-tuples containing allocated channel and power level was designed, and three operation rules for particle were redefined. …