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

Model and Algorithm of Removable Online Mobile Knapsack Problem

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

This paper proposes a removable online mobile knapsack problem,in which a knapsack with some goods needs to serve designated demand points from the starting point.The knapsack should unload the demands and load the goods which need to bring back to the starting point at each demand point,in which the demands are known and the number of good to be loaded are unpredictable.The goal is to find the order of service of demand points and whether to load the goods at each demand point to maximizing the quantity of goods that knapsack brings back to the starting point.By using the online theory and method,this paper establishes the model and designs the online algorithm.By analyzing the difference between the quantity of goods to be loaded and the residual capacity of the knapsack at the demand points,this paper proves the competition ratio and analyses the influencing factors of the competition ratio.The results show that the more of minimize good loading limit,the number of demand points and the amount of good to be loaded at the demand points,the better of the algorithm effectiveness.