可卸货的移动在线背包问题模型和算法

摘要

提出可卸货的移动在线背包问题,即一个装有货物的背包从起点出发对n个指定需求点提供服务,将所装货物在每个点按已知需求量卸下,并将该点数量无法预知的待取回货物装入背包带回起点,如何决策背包对需求点的服务次序及途经需求点是否取回货物,使得取回的货物数量尽可能的多.针对该问题,采用在线理论和方法,建立模型并设计在线算法F,分析需求点待取回的货物数量与背包将该需求点的货物卸下后剩余承载量的差的不同情形,证明F的竞争比并对竞争比的影响因素进行分析,结果表明载货下限越大、需求点个数越多、需求点待取回货物总数越多,算法F的执行效果越好.