物流问题驱动的网络排序研究

With economic globalization and the application of Internet technology, logistics transportation is rapidly enlarging on quantities and fields. The procedure of logistics becomes extremely complex. Scheduling problems based on logistics are increasingly emerging. The network scheduling problems are growing to be a class of important scheduling problems motivated by the practical logistics problems. This project will study the network scheduling problems motivated by the complicated logistics operations from the perspective of combinatorial optimization, especially scheduling. The research of this project consists of AGV network scheduling problems based on vehicle operations, network scheduling problems on logistics transportation and network scheduling problems with time window of logistics distribution. By modeling and analyzing computational complexity and solvability for these problems, we will design efficient polynomial time approximation algorithms or optimal algorithms for the offline problems and provide the online algorithms for online versions. The performance ratio or competition ratio in the worst case will be analyzed and numerical simulations will be done. It is expected that this project will make breakthrough on research methods and get some original results. It will make a contribution to theory and methods of network scheduling and provide theoretical guidance and decision support for solving practical logistics problems.

随着经济全球化和互联网技术的发展与应用，物流运输量大面广，运作程序复杂，基于物流问题的排序越来越多，各类新型网络排序问题正是受实际问题的驱动不断涌现。本项目将从组合优化特别是排序的角度研究复杂物流问题驱动的网络排序问题，主要研究内容有：基于AGV车辆调度的网络排序问题、基于物流运输的网络排序问题和带时间窗物流配送网络排序问题。主要研究这些网络排序问题的数学模型、分析问题的复杂性与可解性、研究可近似性、设计高效的多项式时间近似算法或者最优算法与在线算法、分析算法在最坏情形下的性能比或者竞争比、并进行数值模拟。期望该项目在研究方法上取得突破，得到一些原创性成果，为丰富网络排序的理论与方法做出贡献，同时为解决物流实际问题提供理论指导与决策支持。

根据项目计划，我们主要研究了基于物流实际背景的车辆调度的网络排序问题和基于物流运输的网络排序问题与带时间窗物流配送网络排序问题等。具体内容是：研究了树形网络和环形网络上的返回型和非返回型单机车辆调度的网络排序、在线形网络上的具有不可分割需求的多车辆且有容量限制的路径问题、两代理线形网络上的车辆路径问题、有阈值约束的单机两代理在线形网络上的排序问题、在线两代理排序问题、具有非预期不可用区间的单机排序问题、单机代理排序以及平行机代理排序问题、加工时间与位置有关的两代理排序问题、工件具有学习或退化效应及可拒绝的批排序问题、具有不可用区间的两台机器流水作业问题、有交付时间和有限重启的drop-line平行批处理机上的在线排序问题等。此外，我们还在本项目的支持下，研究了包含不确定信息的专家意见集结问题。对所有这些问题，我们建立了问题的数学模型、分析了问题的复杂性与可解性、设计了高效的多项式时间近似算法或者最优算法与在线算法、分析了算法在最坏情形下的性能比或者竞争比，并通过数值实验来分析所提出算法的性能。我们的研究结果是原创的，这些结果应该能够为解决一些物流实际问题提供理论指导与决策支持。