作者:吴腾宇; 余海燕旅行商问题线性惩罚在线算法需求点应急车辆
摘要:为了在自然灾害之后通过应急车辆尽快地将应急物资送到受灾点,针对每个受灾点在发出需求信号后,不能尽快被应急车辆服务,从而导致受灾点的情形进一步恶化的情形,提出了带有线性惩罚的在线旅行商问题。通过设计最坏序列证明了该问题在一般网络上不存在确定性和随机性的在线算法。针对需求点仅在线段上的情形,分析了问题的下界、设计了推测后再移动策略,并证明了当单个需求点的最大惩罚值大于等于8时,该算法为最优算法。
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社