起重资讯——多车辆塔式起重机问题的近似算法

01行业新闻

远东股份宜宾智慧产业园项目喜迎开工大吉

远东工程副总经理戴海峰，远东股份宜宾智能产业园党支部书记、项目筹建行政后勤组负责人李海东，远东股份高级合伙人、远东电缆（宜宾）项目筹建能源动力组负责人顾庆生，远东股份高级合伙人、远东电缆（宜宾）电缆电气项目筹建技术质量组负责人胡清平，远东电缆（宜宾）项目部土建组负责人李立勇等项目组人员及施工方陕西建工集团有限公司、监理方四川四强建设项目管理有限公司参与本次开工仪式。

远东股份宜宾智能产业园位于南溪区罗龙产业园，占地面积991亩，规划总建筑面积约40万平米，总投资60亿元。园内设“新基建用高端电线电缆研发生产基地”和“新能源车动力电池用高精铜箔研发生产基地”，聚焦公司三大核心业务中的智能缆网、智能电池板块，是集研发、办公、生产、物流于一体的大型现代化产业集群基地。

整个工程项目共分两期进行建设，一期工程项目用地268亩，用于建设3栋生产厂房、一个废品库和一个危废仓库，预计于今年11月份完工并投入使用，12月电线电缆类产品即可投产，2023年1月铜箔类即可投产。

工期紧、任务重，加之疫情影响，项目推进难度可想而知。目标面前不讲条件，任务面前不讲客观，大局面前不讲困难。项目组一切以按期交付为目标，以完成目标为使命！

面对疫情防控要求，项目组坚持一手抓疫情防控，一手抓项目进度，齐心协力为安全施工建设保驾护航，确保打赢疫情防控攻坚战的同时，圆满完成宜宾项目推进目标。

远东股份宜宾智能产业园是公司抢抓发展机遇和品牌红利，进一步扩大市场份额的战略之举，同时也是响应成渝地区双城经济圈发展战略，助力宜宾打造万亿级锂电生产基地的有力举措。项目建成投产后，将成为远东“二次创业”路上强力的引擎，助力实现全球行业“数一不数二”的战略目标。

02钢材指数

1.江苏镔鑫钢铁集团今日价格维稳

4月20日镔鑫钢铁在4月19日的基础上，对建筑钢材价格政策调整：

1、对螺纹钢价格维稳，盘螺价格维稳;

2、现HRB400E螺纹钢Ф25mm苏南地区价格5110元/吨；HRB400E盘螺Ф8-10mm苏南地区价格5390元/吨。

以上调整均含税、过磅。（苏南：南京，无锡，常州，苏州，南通，扬州，镇江，泰州）

2.南钢建筑钢材今日价格涨20

4月20日，南钢在4月19日的基础上，对建筑钢材价格政策调整：

1、对螺纹钢价格上调20元/吨；盘螺价格上调20元/吨；

2、现HRB400螺纹钢Ф16-25mm出厂价格5190元/吨；现HRB400盘螺Ф8-10mm出厂价格5410元/吨。

以上调整均含税。

3.长江钢铁建筑钢材今日价格涨20-30

4月20日，长江钢铁在4月19日基础上对部分产品出厂价进行调整：

1、对螺纹钢价格上调20元/吨，盘螺价格上调30元/吨;

2、现HRB400螺纹钢Ф16-25mm出厂价格5100元/吨；HRB400盘螺Ф8-10mm5380元/吨。

以上调整均含税。

4.首钢长钢建筑钢材今日价格涨20

4月20日，首钢长钢对部分产品出厂价格进行调整：

1、对螺纹钢价格上调20元/吨，盘螺价格上调30元/吨，高线上调30元/吨；

2、现HRB400E螺纹钢Ф18-22mm出厂价格5550元/吨；HRB400E盘螺Ф8-10mm5220元/吨；HPB300高线Φ8-10mm5200元/吨；出厂含税。

5.山东石横特钢建筑钢材今日价格维稳

4月20日，山东石横特钢在4月19日基础上出台建筑钢材价格政策：

1、对螺纹钢价格维稳，盘螺价格维稳;

2、现HRB400E螺纹钢Ф18mm出厂价格5130元/吨；HRB400E盘螺Ф8-10mm5430元/吨。

6.莱钢永锋建筑钢材今日价格维稳

4月20日，莱钢永锋在4月19日基础上出台建筑钢材价格政策：

1、对螺纹钢价格维稳，盘螺价格维稳，线材维稳;

2、现HRB400E螺纹钢Ф18-22mm出厂价格5130元/吨；HRB400E盘螺Ф8-10mm5430元/吨。以上调整均为含税价。

7.江苏雨花建筑钢材今日价格涨20

4月20日，雨花对部分产品出厂价格进行调整：

1、对螺纹钢价格上调20元/吨，盘螺价格上调20元/吨，高线上调20元/吨；

2、现HRB400螺纹钢Ф18-20mm出厂价格5100元/吨；HRB400盘螺Ф8-10mm5340元/吨；HPB300高线Φ8-10mm5320元/吨；出厂含税。

03起重创新

多车辆塔式起重机问题的近似算法

戴瑞勇

华东理工大学

摘要：随着社会的发展与进步,物流调度、路径导航和无人驾驶等技术在日常生产生活中起着越来越重要的作用,吸引了众多数学和经济学家的关注。本文研究了多车辆情况下的塔式起重机问题（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）时间内运行。