数学季刊 ›› 2026, Vol. 41 ›› Issue (1): 38-49.doi: 10.13371/j.cnki.chin.q.j.m.2026.01.003

• • 上一篇    下一篇

航空器供油问题的优先准则及梯度排序算法

  

  1. School of Mathematics and Statistics, Henan University of Technology, Zhengzhou 450001, China
  • 收稿日期:2025-02-13 出版日期:2026-03-30 发布日期:2026-03-30
  • 作者简介:LIN Hao (1974-), male, native of Taishan, Guangdong, MSc, associate professor of Henan University of Technology, engages in network optimization; HE Cheng (1975-), female, native of Xinyang, Henan, PhD, professor of Henan University of Technology, engages in combinatorial optimization.
  • 基金资助:
    Supported by Natural Science Foundation of Henan Province (Grant Nos. 232300421218 and 252300421483).

Precedence Criteria and Gradient-Based Scheduling Algorithm for the Airplane Refueling Problem

  1. School of Mathematics and Statistics, Henan University of Technology, Zhengzhou 450001, China
  • Received:2025-02-13 Online:2026-03-30 Published:2026-03-30
  • About author:LIN Hao (1974-), male, native of Taishan, Guangdong, MSc, associate professor of Henan University of Technology, engages in network optimization; HE Cheng (1975-), female, native of Xinyang, Henan, PhD, professor of Henan University of Technology, engages in combinatorial optimization.
  • Supported by:
    Supported by Natural Science Foundation of Henan Province (Grant Nos. 232300421218 and 252300421483).

PDF (PC)

0

摘要：

The airplane refueling problem can be stated as follows. We are given n airplanes which can refuel one another during the flight. Each airplane has a reservoir volume wj (liters) and a consumption rate pj (liters per kilometer). As soon as one airplane runs out of fuel, it is dropping out of the flight. The problem asks for finding a refueling scheme such that the last plane in the air reach a maximal distance. An equivalent version is the n-vehicle exploration problem. The computational complexity of
this non-linear combinatorial optimization problem is open so far. This paper employs the neighborhood exchange method of single-machine scheduling to study the precedence relations of jobs, so as to improve the necessary and sufficiency conditions of optimal solutions, and establish an efficient heuristic algorithm which is a generalization of several existing special algorithms.

关键词: Combinatorial optimization, Scheduling method, The Airplane Refueling Problem, Optimality criteria, Heuristic algorithm

Abstract:

The airplane refueling problem can be stated as follows. We are given n airplanes which can refuel one another during the flight. Each airplane has a reservoir volume wj (liters) and a consumption rate pj (liters per kilometer). As soon as one airplane runs out of fuel, it is dropping out of the flight. The problem asks for finding a refueling scheme such that the last plane in the air reach a maximal distance. An equivalent version is the n-vehicle exploration problem. The computational complexity of
this non-linear combinatorial optimization problem is open so far. This paper employs the neighborhood exchange method of single-machine scheduling to study the precedence relations of jobs, so as to improve the necessary and sufficiency conditions of optimal solutions, and establish an efficient heuristic algorithm which is a generalization of several existing special algorithms.

Key words: Combinatorial optimization, Scheduling method, The Airplane Refueling Problem, Optimality criteria, Heuristic algorithm

中图分类号: 

版权所有 © 《数学季刊》编辑部
地址：河南省开封市明伦街85号河南大学数学季刊编辑部
电话：0371-23881698　E-mail: sxjk@henu.edu.cn　QQ: 2454327236
本系统由北京玛格泰克科技发展有限公司设计开发　技术支持：support@magtech.com.cn