Scholarlink

We address the Single School Routing Problem (SSRP) by proposing an optimized approach balancing efficiency and transportation safety. As an NP-hard variant of the Vehicle Routing Problem (VRP), SSRP aims to minimize total travel distance while satisfying vehicle capacity and time constraints. Existing approaches, such as adaptive large neighborhood search (ALNS), often generate irrational route sequences that may increase students’ maximum riding time. To tackle this issue, a novel mixed integer programming (MIP) model is introduced, and a hybrid adaptive large neighborhood search (HALNS) algorithm is designed. The MIP model eliminates irrational routes passing through the school via constraint conditions. HALNS efficiently explores the solution space using five destruction operators and three repair operators, and adjusts the visiting order via shortest maximum riding time ant colony optimization (SMRTACO). Practical case calculations demonstrate that the new model improves solving speed and quality when using Gurobi. HALNS outperforms solvers like CPLEX and Gurobi, as well as ALNS, in terms of solution quality and runtime. Specifically, HALNS reduces the maximum riding time by up to 15.3%, ensuring safer and more direct routes to enhance student transportation safety. The method verifies its effectiveness in balancing efficiency and safety across small-, medium-, and large-scale datasets.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Hybrid Adaptive Large Neighborhood Search for Secure and Efficient Single School Routing Problem

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Zhangwei Cui,
  • Yitao Chen,
  • Qiongbing Zhang,
  • Rui Pang

摘要

We address the Single School Routing Problem (SSRP) by proposing an optimized approach balancing efficiency and transportation safety. As an NP-hard variant of the Vehicle Routing Problem (VRP), SSRP aims to minimize total travel distance while satisfying vehicle capacity and time constraints. Existing approaches, such as adaptive large neighborhood search (ALNS), often generate irrational route sequences that may increase students’ maximum riding time. To tackle this issue, a novel mixed integer programming (MIP) model is introduced, and a hybrid adaptive large neighborhood search (HALNS) algorithm is designed. The MIP model eliminates irrational routes passing through the school via constraint conditions. HALNS efficiently explores the solution space using five destruction operators and three repair operators, and adjusts the visiting order via shortest maximum riding time ant colony optimization (SMRTACO). Practical case calculations demonstrate that the new model improves solving speed and quality when using Gurobi. HALNS outperforms solvers like CPLEX and Gurobi, as well as ALNS, in terms of solution quality and runtime. Specifically, HALNS reduces the maximum riding time by up to 15.3%, ensuring safer and more direct routes to enhance student transportation safety. The method verifies its effectiveness in balancing efficiency and safety across small-, medium-, and large-scale datasets.