戴瑞勇
华东理工大学
起重电机专业生产厂家无锡宏达2022年4月23日讯 随着社会的发展与进步,物流调度、路径导航和无人驾驶等技术在日常生产生活中起着越来越重要的作用,吸引了众多数学和经济学家的关注。本文研究了多车辆情况下的塔式起重机问题（Stacker Crane Problem）,提出了相应的近似算法。问题的输入由一个包含顶点集V,边集E和弧集A的混合图G=（V,E,A）和一个定义在E∪A上的非负整数费用函数c组成。根据不同的优化目标,本文考虑以下四个问题:
（一）k-仓库塔式起重机问题（k-DSCP）。给定一个包含k个不同仓库点的集合D（?）V,目标是找到一系列包含弧集A中所有弧的k条回路（closed walks）且使得回路的总费用最小。每条回路对应一个车辆的行驶路线,并且必须从一个不同的仓库点出发再返回到这个仓库点。
（二）k-塔式起重机问题（k-SCP）。不给定固定仓库点,车辆可以从任意顶点出发,然后返回相应的出发点。目标是找到一系列包含弧集A中所有弧的k条回路且使得回路的总费用最小。
（三）k-仓库塔式起重机路问题（k-DSCPP）。给定一个包含k个不同仓库点的集合D（?）V,目标是找到一系列包含弧集A中所有弧的k条路径（open walks）且使得路径的总费用最小。车辆必须从一个不同的仓库点出发但可以在任意顶点停下。
（四）k-塔式起重机路问题（k-SCPP）。不给定固定仓库点,车辆可以从任意顶点出发,也可以在任意顶点停下。目标是找到一系列包含弧集A中所有弧的k条路径且使得路径的总费用最小。
针对以上四个问题,本文分别提出了常数界的近似算法。具体来说,针对k-DSCP、k-SCP和k-DSCPP,本文首先分别给出了一个3-近似算法。如果弧费用是对称的,即对于图G中的每条弧,G中都有一条费用不大于这条弧的平行边,本文分别给出了具有更好近似比的算法。算法的近似比分别为max{9/5,2-1/2k+1}、2和2。对于k=SCPP,本文首先给出了一个针对弧费用满足对称性条件的2-近似算法。接着,对于k-SCPP在k=1时的一个特例,即SCPP,本文给出了一个适用于所有实例的3-近似算法和一个针对弧费用满足对称性条件的9/5-近似算法。其中,除了三个2-近似算法的复杂度为O（|V|2log|V|）,上述所有算法均可以在O（|V|3）时间内运行。
|
