（管理科学与工程专业论文）有先后顺序限制或时间窗口限制的线性往返问题研究.pdf

，i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 霞延簿 日期：砰歹月z f 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将 学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被 套阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或 其他方法保存学位论文， 学位论文作者签名：燃 f 1 期：砷年期加 翩妣融旋 日期洲年j ，月甜日 有先后顺序限制或时间窗口限制的线性往 返问题研究 专业：管理科学与工程 硕士生：顾延德 指导教师：石风波副教授 摘要 在集装箱港口，泊位沿直线分布，到达的船只停泊在泊位处等待港口机械的 服务。由于各种运输工具的载重量不同，所以到达港口的集装箱必须在集装箱货 场堆放，以便按时装卸。在货场上，各集装箱货堆在货场上排列成网格状，前后 左右留有拖车运行通道。由于外部集装箱到达时间的不确定性，所以集装箱无序 的摆放在指定的货堆中。负责集装箱提取和摆放的卡吊在货堆内沿既定轨道来回 直线移动，按照要求顺序进行提货。负责托运的拖车在通道内来回搬运集装箱， 为了避免货场上交通拥挤，拖车在货堆内沿直线进行搬运。而对于港口泊位中的 船只来说，当未到服务时间时，只能在泊水区等候命令，直到到达规定的服务时 间时，才能入港接受服务。 有先后顺序限制的线性往返问题描述的是对于货场上集装箱，为了减少集装 箱在船上的倒垛和搬运过程，所以在集装箱提取时，要按照一定的顺序对其进行 提取。其模型可以描述为，对于排列在一条直线上的节点，存在着先后访问顺序 的限制，目的是去寻找一条最优访问顺序，使所走过的路径最短。在本论文中， 我们讨论了存在单一先后约束的情况和多个约束的情况。对于单一约束的有先后 顺序限制的线性往返问题，我们提出了其拥有的优化性质，在此基础上给出了快 速有效的求解算法。对于有多个约束的有先后顺序限制的线性往返问题，我们证 - 明此类问题是多项式时间内可解的，而且我们证明了其具有动态规划的性质，可 以利用动态规划进行求解。 有时间窗口限制的线性往返问题描述的是泊位上集装箱船服务的情况，其 模型可以描述为，对于排列在一条直线上的节点，存在着访问时间的限制。每个 节点存在着最早开始访问时间、最迟结束时间以及服务时间。对于有时间窗口限 制的线性往返问题，我们首先证明它是n p - h a r d 问题。在此基础上，我们建立了 有时间窗口限制的线性往返问题的数学模型，并给出它的数据实验设计。在数据 实验设计中，节点的服务时间窗口分为固定的服务时间窗口和随机的服务窗口。 为了证明算法的有效，我们把其结果和c p l e x 的标准结果进行对比。对于固定的 时间窗口，我们提出一种启发式的排序算法进行求解，并且对于是否存在可行解， 我们给出了数学证明；而对于可变时间窗口，我们利用蚁群算法进行求解，并且 根据问题的具体特性，对蚁群算法进行了改进，提高算法的收敛速度。 关键字：线性往返启发式排序蚁群算法 l i l i n e a rs h u t t l i n gp r o b l e m sw i t hp r e c e d e n c e c o n s t r a i n t so rt i m ew i n d o w sc o n s t r a i n t s m a j o r ：m a n a g e m e n ts cie n c ea n de n g in e e r in g n a m e ：y a n d eg u s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rf e n g b os h i a b s t r ac t o nt h ec o n t a i n e rp o r t ，t h eb e r t h sa r el o c a t e di nal i n e a rl i n e t h e c o n t a i n e rs h i p sa r ew a i t i n gf o rt h es e r v i c en e a rt h eb e r t h s b e c a u s eo f t h ed i f f e r e n c ei nc a r r y i n gc a p a c i t yo fd i f f e r e n tt r a n s p o r tv e h i c l e s ，t h e c o n t a i n e r sa r r i v e dm u s tb el o a d e do nt h eg r o u n dw h i c hi sa no p e np l a c e f o rt h ec o n t a i n e rf o rt h ep u r p o s eo fl o a d i n go nt i m e o nt h ec o n t a i n e r g r o u n d ，t h ec o n t a i n e rp il e sa r ea ll o c a t e d1i k ea n e t a r o u n dt h ec o n t a i n e r p il ea r et h er o u t ew a y s b e c a u s eo ft h eu n c e r t a i n t yo ft h ea r r i v i n gt i m e o fc o n t a i n e r ，t h ec o n t a i n e r sp l a c e di nt h ec o n t a i n e rp il e sa r er a n d o ma n d u n a r r a n g e d t h ec r a n e sw h i c ha r er e s p o n s i b l ef o rl o a d i n ga n du n l o a d i n g t h ec o n t a i n e r sw o r ko nt h eli n e a rt r a c k s ，a c c o r d i n gt ot h er e q u e s to ft h e s e q u e n c e t h et r a i lc a r sr e s p o n s i b l ef o rc a r r y i n gc o n t a i n e r sc a r r yt h e c o n t a in e r so nt h er o u t ew a yg oa n df o r t h f o rt h ep u r p o s eo fag o o dt r a f f ic ， t h et r a ilc a ro nt h ec o n t a i n e rg r o u n dr u n sd i r e c t l ya n da v o i dt u r n so n t h er o u t ew a y f o rt h ec o n t a i n e rs h i p ，i tc a n tb es e r v e du n t i lt h et i m e s a t i s f i e st h er e q u i r e m e n to ft h ea r r a n g e m e n t w h e ni td o e sn o ts a t i s f y t h et i m er e q u i r e ，t h es h i pm u s ts t a yo u t s i d et h eb e r t hf o rt h eo r d e r w h e n t h et i m es a t i s f i e s ，t h es h i pa c c e p t st h es e r v i c e l i n e a rs h u t t l i n gp r o b l e m sw i t hp r e c e d e n c ec o n s t r a i n t si sa b o u tt h e c o n t a i n e r so nt h eg r o u n d t or e d u c et h ec o u r s e so fc a r r y i n gl o a d i n ga n d u n l o a d i n go nt h es h i p ，i tm u s tb ea c c o r d i n gt ot h es e q u e n c eo fa r r a n g e m e n t w h e ni tb e g i n st op i c ku pt h ec o n t a i n e r s t h em o d e li st h a tt h e r ea r es o m e n o d e sa l l o c a t e di nal i n e rl i n ea n dw i t hp r e c e d e n c ec o n s t r a i n t s t h e o b j e c t i v ei st of i n dao p t i m a lr o u t et om a k et h el e n g t ho ft h er o u t em i n i m u m i nt h i sp a p e r ，w et a l ka b o u tt h ep r o b l e mw i t hs i n g l ec o n s t r a i n ta n d m u lt i p l ec o n s t r a i n t s f o rt h es i n g l ec o n s t r a i n tp r o b l e m ，w ef i n di ta n o p t i m a lp r o p e r t ya n da c c o r d i n gt ot h ep r o p e r t y ，w eg i v eaq u i c ka n d e f f e c t i v es o l u t i o nt oi t f o rt h em u l t i p l ec o n s t r a i n t sp r o b l e m ，w ep r o v e t h a ti tc a nb er e s o l v e di np o l y n o m i a lt i m ea n di th a st h ep r o p e r t yo f d y n a m i cp r o g r a m m i n g ，s ow ew i l lu s et h ed y n a m i cp r o g r a m m i n gt os o l v ei t l i n e a rs h u t t li n gp r o b l e m sw i t ht i m ew i n d o w si sa b o u tt h ec o u r s eo f l o a d i n gt h ec o n t a i n e r s t h em o d e li st h a t ，t h en o d e sa ll o c a t e di nali n e a r 1 i n eh a v et h et i m ec o n s t r a i n t s e a c hn o d eh a st h ee a r l l e s ts t a r tt i m et h e l a t e s tf i n i s ht i m ea n ds e r v i c et i m e f o rt h ep r o b l e mw i t ht i m ew i n d o w s ， w ef i r s tp r o v et h a t ，itisn p h a r d t h e n ，w ec o n s t r u c tt h em o d e lo ft h e p r o b l e ma n dw eg i v et h en u m e r i c a le x p e r i m e n td e s i g n i nt h ed e s i g n ，t h e t i m ew i n d o w sa r ec l a s s i f i e da sf i x e dt i m ew i n d o wa n dr a n d o mt i m ew i n d o w f o rt h ee f f e c t i v e n e s so ft h es o l u t i o n ，w ew i11 c o m p a r et h er e s u l t sw i t h t h es t a n d a r dr e s u l t sf r o mc p l e x f o rt h ef i x e dt i m ew i n d o w ，w eg i v ea h y b r i ds o r t i n gh e u r i s t i ct os o l v ei t a n df o rw e a t h e rt h e r ei saf e a s i b l e s o l u t i o n ，w eg i v eap r o o f f o rt h er a n d o mt i m ew i n d o w ，w eu s et h ea n tc o l u m s y s t e mt os o l v ei t a c c o r d i n gt ot h ep r o p e r t yo ft h ep r o b l e m ，w ei m p r o v e t h ea l g o r it h ma n de n h a n c et h er a t eo fc o n v e r g e n c e k e y w o r d s ：l i n e rs s y s t e m 目录 摘要i a b s t r a c t i i i 第一章引言1 1 1 选题背景。1 1 2 问题描述4 1 3 研究的意义6 1 4 文献综述9 1 5 论文设计1 2 第二章问题模型。1 4 2 1 一般的线性往返问题1 4 2 2 有先后顺序限制的线性往返问题1 6 2 3 有时间窗口限制的线性往返问题2 1 第三章蚁群算法2 s 3 1 引言2 5 3 2 蚁群算法的思想。2 7 3 3 蚁群算法模型的人工抽象2 9 3 4 人工蚂蚁的设置3 0 3 5 基本蚁群算法的数学模型3 2 第四章数据实验3 7 4 1 数据实验设计3 7 4 2 固定时间窗口实验设计3 8 4 3 可变窗口实验设计4 2 4 4 实验结果4 3 第五章结论与展望4 8 5 1 问题总结。 s 2 未来展望5 0 参考文献s l 附j 素：5 5 致谢：5 6 v 图目录 图卜1 集装箱港口4 图卜2 集装箱货场5 图卜3 集装箱目的港口5 图卜4 港口泊位服务6 图2 1 集装箱货场1 4 图2 2 集装箱货堆简化图1 5 图2 3 集装箱货堆图1 7 图2 4 集装箱货堆简化图1 7 图2 5 单一约束例子1 9 图2 6 单一约束解法2 0 图2 7 时间窗口约束简图2 l 图3 一l 双桥实验示意图2 5 图3 2 双桥实验结果示意图2 6 图4 1 数据实验设计3 7 图4 2 启发式排序算法流程图3 9 图4 3 启发式排序算法示例( 1 ) 4 0 图4 4 启发式排序算法示例( 2 ) 4 0 图4 5 启发式排序算法证明( 1 ) 4 0 图4 6 启发式排序算法证明( 2 ) 4 l 图4 7 算法消耗时间4 5 图4 8 固定时间窗口结果4 5 图4 9 固定时间窗口路径长度4 6 图4 一1 0 可变时间窗口路径长度4 6 1 1 选题背景 第一章引言 港口是海一陆联运的枢纽点，是海一陆运输的连接点之一。全球货物贸易运输 量的8 0 是经由港口实现的，在中国，8 5 的贸易是由港口实现的。港口已经成 为支撑国际贸易发展的重要基础设施，在全球资源流通和贸易发展中发挥着日益 重要的作用。集装箱化率的提高使世界港口运输业发展更为迅速，集装箱运输在 过去的5 年里以每年1 2 4 的惊人速度增长，根据港口统计原则，2 0 0 4 年超过3 亿t e u ，其中包括空箱和转运箱 1 。但中国的集装箱化率只有6 0 ，与集装箱化 强国的9 0 l i , 率还差很大一段距离，所以发展中国的集装箱化就成为中国“十一 五 期间港口建设的重要目标。 目前，中国对外贸易的8 5 是通过港口实现的，而在经济全球化大发展的趋 势下，中国“世界工厂 地位的确立和对国际资源的依赖，都会产生巨大的运输 需求，这些无疑会给我国的集装箱运输业带来新的发展机遇，提供充足的发展空 间。近十几年来，在外贸新一轮高速增长、集装箱化率提高和集装箱港口建设加 速三大因素推动下，中国集装箱市场空前繁荣，货物吞吐量突破4 0 亿吨，增长 2 1 3 ，其中集装箱吞吐量达到6 1 5 0 万t e u ，增长2 6 4 。克拉克森数据显示： 到2 0 1 0 年，世界港口集装箱吞吐总量可能达到4 0 7 亿一4 2 5 亿t e u ，其中亚洲 地区港口集装箱吞吐量占全球市场份额将由2 0 0 0 年的4 7 5 上升至5 5 一6 0 ，而 中国是主要的业务增长点和最大的集装箱货源生成地 1 。 以厦门港口为例，在从1 9 9 4 年到2 0 0 5 年这一段时间内，集装箱的吞吐量成 倍增长，到2 0 0 7 年已经达到约4 6 3 万标箱 2 ，估计到2 0 1 0 年，将会是2 0 0 5 年 的一倍，达到7 0 0 万标箱左右。 表1 - 1 厦门港口集装箱吞吐量记录 期数年份吞吐量期数年份吞吐量 11 9 9 42 272 0 0 01 0 8 21 9 9 53 182 0 0 11 2 9 31 9 9 64 092 0 0 21 7 5 41 9 9 75 41 02 0 0 32 3 3 51 9 9 86 51 l2 0 0 42 8 7 61 9 9 98 51 22 0 0 53 3 4 3 为了满足迅速增长的港口运输需求，近年来我国港口集装箱码头的建设全 面加快，港口吞吐量逐年增加，港口作业实现全面机械化，有效、快速的完成装 卸作业。下表是我国主要港口2 0 0 7 年货物吞吐量和集装箱吞吐量排名表 3 。交 通部已经确定目标，到2 0 1 0 年，我国沿海港口集装箱吞吐能力要达到l 亿t e u 以上。 表1 2 我国主要港口2 0 0 7 年吞吐量排名 2 0 0 7 年我国主要港口货物吞吐量和集装箱吞吐量排名 集装箱吞吐量( 万标箱)货物吞吐量( 亿吨) 排序港口吞吐量港口吞吐量 l 上海2 6 1 5 0 0上海 5 6 2 深圳 2 1 0 9 9 1宁波一舟山4 6 8 3 青岛 9 4 6 2 0广州3 4 1 4 宁波一舟山 9 3 6天津3 0 9 5 广州 9 2 0 0 0青岛2 6 5 6 天津 7 1 0 2 9秦皇岛 2 4 5 7 厦门 4 6 2 7 0大连2 2 8 大连3 8 1 3 0深圳2 0 9 连云港 2 0 0 0 6苏州1 8 4 1 0 营口 1 3 7 1 3日照1 3 1 2 另一方面，传统的港口集装箱作业已经在装卸工艺、生产管理和信息服务方 面都已经成为制约集装箱码头能力的瓶颈。伴随着集装箱吞吐量的大幅度增长， 我国港口的建设规模逐步加大，逐步实现全面机械化，并向信息化方向发展，港 e l - l _ 作效率得到进一步提高。然而港口严重拥挤、集装箱船无法准时装卸的问题， 仍是我国集装箱港口面临的一个巨大挑战。以新加坡和上海港口为例 4 ，上海港 作为中国的第一大港，在港口现代化的过程中一直处于领先地位。新加坡是世界 著名的中转港，其机械化和信息化水平世界领先。下表是上海和新加坡港口集装 箱停留时间的比较，新加坡港口集装箱的停留时间远小于中国的上海港，中国港 口的作业效率需要进一步提高。 表1 3 上海和新加坡港口集装箱停留时间比较 耗费时间( f f 钟) 活动上海新加坡 船舶到港口 1 01 4 港口到园区 3 06 5 园区内集装箱储 9 0 6 5 存 不拆箱检查 园区内集装箱回 4 8 01 9 0 收拆箱检查 1 9 2 0 l o 小时1 0 分( 8 ) 合计3 4 小时1 0 分( 9 2 )5 小时3 4 分 在现有的作业条件下，如何提高港口集装箱的装卸效率，如何充分利用港口 货场的存储能力，以及如何提高货场作业效率，就成为每个港口人员的关注重点， 也是港口研究的热点。 3 1 2 问题描述 下图是集装箱码头的图片，等待装船出港的集装箱堆在货场上，负责提取集 装箱的卡吊在集装箱货堆中来回移动，取出集装箱，搬运到拖车上，由拖车运到 港口泊位，最后由泊位上的岸桥装上集装箱船。而到达的集装箱，则有拖车负责 托运到货场，放到指定的区域，以便以后集装箱能迅速的装卸，提高港口的运作 效率 5 。 图卜1 集装箱港口 有先后顺序限制的线性往返问题 在集装箱港口的选址和建设当中，除了要考虑运距和成本因素外，还必须考 虑港口的经济地理位置、地理条件、与腹地联系和港口自然条件等因素。但在现 实中，由于港口具有天然性的缘故，人工造港要花费很大的人力物力，所以港口 在实际运营过程中就存在着可用面积的限制。由于各种运输工具的装载量不同， 到达的时间又不一致，例如集装箱船是按班期的时间表到港的，其装载量很大， 最大的船舶转载量达8 0 0 0 - 1 0 0 0 0 t e u ，而公路运输的拖车是不定期到达的，每两 拖车只能装卜2 t e u 1 。因此集装箱船上卸下的大量集装箱要在码头上保存一段 时间，而要通过集装箱船出港的大量集装箱就要提前运入，这就需要一定的场地 来进行堆放。 下图是香港港口的货场图片，货场中，集装箱按照规定，以网格状堆放在货 4 场上，前后左右有运输通道，以便拖车进行出入。而负责提取的轮吊在预定的轨 道上进行提取操作，然后由拖车拖到港口泊位。 图卜2 集装箱货场 但在实际中，由于同一目的地港口的集装箱送达港口的时间不尽相同，除了 直达的集装箱船之外，一般情况下，一艘集装箱船要经过多个中转港，最后到达 目的地。所以在货场中，同一班期的集装箱可能分放在不同货堆，所以货场在安 排装卸货物时，就要考虑拖车来回运行的距离，以提高拖车的利用效率的效率。 下图是集装箱船从大连港出发，途经上海、香港、新加坡，最后到达南非的 开普敦；另一条是直接从香港出发，直达日本东京港。对于直达的集装箱船，一 般只根据集装箱的特性进行装卸，如是否是冷冻集装箱或者是一些特殊物质的集 装箱，如有毒液体或医药等。对于长途集装箱船，船体中不备有装卸器械，所以 船上的倒垛搬运是一件耗费力气的事情，费时费力，效率低下。所以在集装箱装 船时，就要根据到达港口的顺序，进行合理装载( 这里我们不去考虑船体上如何 摆放，船体平衡等问题) 6 。我们假设集装箱在集装箱船上按到达目的地港口 进行摆放，在集装箱装卸时，就要考虑集装箱的装卸顺序，以减少集装箱在船上 的倒垛搬运次数，加快装卸速度，提高效率。 图卜3 集装箱目的港口 5 有时问窗口限制的线性往返问题 集装箱港口需要有宽大的港口面积，同时也要考虑港口以后的扩展，面积过 小，会影响港口的作业效率。为此，集装箱港口应采用顺岸式，在建设多泊位港 口时，应布置连续泊位，这样有利于机械的调配，以节约码头资源。在港口集装 箱作业区内，装卸桥或岸桥停泊在泊位上，对到港的船只进行装卸服务。而未到 服务时间的集装箱船，就停泊在泊水区，直到允许，才进入港口泊位进行服务； 如果超过服务时间的集装箱船只，由于航线的时间限制，理论上是必须强制离港， 但实际上是通过采用其他惩罚措施进行补救的，如延迟到达目的港口，从而造成 信用损失或雇主和客户的损失。或者调用更多的机械装备进行装卸，耗费更多的 人力与物力。所以港口泊位集装箱的装卸过程，就是要满足时间窗口约束的线性 往返问题。如下图所示，岸桥停在泊位上，集装箱船停靠在泊位附近，岸桥强有 力的两臂将集装箱慢慢运送到集装箱船上。当一个泊位服务完成时，岸桥沿着预 设的轨道移向另一个需要服务的泊位，对其进行服务。 1 3 研究的意义 图卜4 港口泊位服务 现代港口是资源配置中心，是一个国家对外经济的起点，具有运输、商业、 贸易、工业和旅游等多种功能。充分发挥港口优势，大力发展临港工业、物流、 商贸为重点的港口经济，便于利用国内外两种资源和两个市场，繁荣本国经济， 6 尤其是在金融危机出现以后。现代港口具有成本低、领域宽、潜力大、规模经济 显著、竞争力强、发展前景广阔等特点，对于港口城市的崛起和金融危机后的经 济发展具有及其重要的作用。而现在，亚洲在全球航运业中占据了领导地位，世 界上最大的2 0 个集装箱公司中的1 3 个是亚洲公司，而这1 3 个亚洲公司控制着 全球t e u 运力的7 0 1 。从世界上大型航运公司所在的地理位置上可以看出世 界运输中心正在从西方转移到东方。中国在这一变化中起着决定作用，最近十年， 集装箱的吞吐量增长速度达到3 0 1 ，在增长速度方面居世界首位。 随着三大集装箱枢纽港群的建设，集装箱的吞吐量和工作效率会有极大的提 高。北方枢纽港群以大连港、天津港和青岛港为主。大连港是东北地区的出海门 户，随着振兴东北老工业基地战略的实施，东北地区的经济和对外贸易的恢复和 发展，为大连港提供充足的货源，同时它本身的工作效率问题，尤其在装卸报关 方面，虽然有自身体制的问题，但装卸上的效率问题，一直是港口发展的制约。 最近大连港同新加坡港口合作，新加坡港口为大连港口提供高效的电子信息化技 术，将会对大连港的发展起到巨大的促进作用 6 。天津港位于渤海湾的内部， 是京津唐地区的出海口，是终端型的大型集装箱港口，是山西、陕西、内蒙古等 地的出海区，随着资源的紧缺，其贸易量逐年增加，是北方港口中增长速度最快 的港口之一，尤其是在集装箱方面，但其装卸效率等问题一直制约着天津港的发 展，尤其是在出现紧急情况时，就要进行额外调度。青岛港位于胶东半岛的东部， 呈半拥抱状态，港深、腹地广阔，地理位置优越，是东北亚地区的第二大中转枢 纽港，有望超过韩国釜山港，成为东北亚最大的中转港。东部枢纽港以上海港、 宁波港为中心，形成辐射状发展。上海港依托中国第一大城市和位于长江、沿海 交汇处的地理位置优势，一直占据我国货物、集装箱吞吐量第一大港的位置，尤 其是洋山港口的建设，更是如虎添翼，为上海港的持续发展提供不竭的动力。而 宁波港和江苏诸港口以上海港为中心，形成国际航运中心的两翼。南部枢纽港以 广州、香港和深圳为主 1 。香港虽有先进的管理技术等优势，但其岸线紧缺， 装卸费用高，货源不足以及地域狭小等条件制约，最近发展缓慢。深圳港凭借其 地理位置和货源优势，装卸费用低，同时学习香港港口的先进管理技术，尤其在 信息化方面，正在逐步实现高效化，提高港口的作业效率。广州港因处于珠三角 经济中心，有其发展的优势。 7 虽然中国三大枢纽港群正在逐步形成，中国的航运业领导地位举世公认，但 中国港口自身存在的问题也不容忽视。虽然中国通关过程有其自身要求，造成效 率低下，但港口工作效率低下的问题不能以通关过程掩盖而过。中国港口虽然也 逐步进行信息化，但相对于日本、新加坡等国的港口而言，还是处于起步阶段。 原因一部分是由于自身的经济原因，起步晚，所以一直处于一种跟跑的状态；另 外一个原因就是港口人员的信息化水平的问题，信息系统的利用效率不高，以及 操作不熟等原因，使港口工作的很大程度依赖于经验。所以港口作业效率等问题 就成为诸多学者研究的热点，而本文研究的问题是旅行商问题的转化形式，以有 时间窗口约束的线性往返问题为重点进行研究。 旅行商问题描述的是一个旅行商经过所有城市，每个城市经过一次且仅一次 的情况下，所走路程最短的问题，这些城市在平面空间中呈随机分布。如果这些 城市在平面空间内沿一条直线分布，就变成旅行商问题的转化问题，线性往返问 题。在大型集装箱码头，不同吨位的泊位沿着港口直线排开，而负责装载和卸货 的岸桥或者是装卸桥在泊位中沿直线移动，在满足装载时间限制的基础上，也就 是在港口装卸服务允许的时间范围内，尽力完成所有装卸任务，在此基础上，实 现所走路径的最短。而在后场或者货场中，由于集装箱到达港口的时间不同，而 同一班期的集装箱安排在货场的同一货堆中，所以使集装箱的堆放处于一种无序 状态，对于同一班期的到不同港口的集装箱而言，就要进行有顺序的进行装卸， 以减少在船上倒垛、搬运的过程。所以根据轮船港口到达的先后顺序来进行货场 集装箱的提取。在货场上，卡吊或者轮吊沿着直线轨道移动进行提取，按照先后 顺序进行作业，实现所走的路径最短。而负责托运送的拖车，就要在入口和出口 之间来回移动，将集装箱放到指定位置，从而实现所走路径最短。 在作业过程中，由于每个节点( 泊位) 和货场装卸，被赋予了先后顺序的限 制或者是时间窗口的约束，所以在作业过程中就要尽量满足约束要求。由于本论 文中所研究的距离是沿着直线计算，所以在假设吊车运行速度一定的条件下，就 可以转化成求时间最短的问题。本文的研究是在将实际问题抽象成模型后，给出 有效的算法，以在有限的时间内，提高工作效率。 8 1 4 文献综述 有限制的线性问题是一般旅行商问题的变形，其变形体现在两个方面：其一 是其距离结构是直线距离 7 ，而不是旅行商问题中的平面结构，从而在一定程 度上来说，l s p 是旅行商问题的特例，而且其解容易；另外一个转换就是有先后 顺序限制或时间窗口限制 8 ，这些约束增加了l s p 问题的难度，很难解决，所 以对l s p 复杂度和其解决方法在现在所能查到的所有的文献中暂时还没有，所 以本文将会用启发式排序算法和蚁群算法解决这些问题。 旅行商问题是世界公认的n p - h a r d 问题，对于它的解法，不同的研究者给出 了不同的解法。对于t s p 问题，除了t s p 的一些特例研究外，另外一方面就是有 关于t s p 限制问题研究，而最常见的又是顺序限制和时间窗口限制，因为t s p p c 和t s p - t w 是t s p 问题的延伸，所以很多学者都致力于这方面的研究。c a l v or w 于2 0 0 0 年利用局部搜索和局部插入的出启发式算法来求解t s p 问题。s u n g c h u l h o n g 等于2 0 0 2 年采用并行的插入方法进行分组和排序，求解双目标的线性模型 v r p - t w 问题。z h a n gq w 等于2 0 0 8 年利用智能蚁群算法和动态规划方法求解 v r p - t w 问题。m i n g o z z i 等 9 提出了利用动态规划的方法来求解t s p - t w p c 问题，其算法采用一个有界函数来界定区域空间，从而加快问题解的求解。m o o n 等 1 3 利用遗传算法来解决t s p - p c 问题，f o c a c c i 等在2 0 0 2 年利用启发式算 法求解t s p - t w 问题 1 0 ，其利用有界性和遗传算法的交叉遗传等方法进行求解。 虽然对于t s p 的特例和延伸有诸多研究，但越来越多的研究方法倾向于启发式算 法，而蚁群算法在解决t s p 的特例和延伸问题上体现了其无比的优越性。 1 9 9 6 年，d o r i g om 等在 扎同理，我们定义集合三，l = p i - p 1 0 x j 。所以 集合i 就可以表示成由尸，r 和三组成，也就是i = p u r u 三。设r m 表示离开 始节点最远的节点，即r m = 刀) ，很明显r = 或者r m r 接下来我们将给出有先后顺序限制的l s p 的一优化性质： 性质一：如果l s p p c 问题存在可行解，而且r ，那么，必存在一个最 优解。而且，最优解的顺序是( 一即，) 。其中，代表集合r 中的元素。 因为上式的结论很明显，所以我们就不给出正规的证明，只给出一个简单的 说明。性质一是说，如果l s p - p c 问题存在可行解，那么就存在一个最优解，当 访问完节点即之后，卡吊就可以按顺序从左到右访问集合足中的节点。因为集 合足不含有任何有约束的节点，而且从即到r m 时，再由r m 回到即时，按顺 序访问，路径最短，所以性质一是完全合理的。 根据性质一，我们可以暂时不考虑集合尺中的元素，或者说将它移走。当我 们有了集合，一r 的最优解时，我们只要加入集合足，就可以确定最后的最优解。 而且进一步，我们可以考虑移走集合中的元素。因为当我们在对集合尸进 行访问时，当它到达节点r p 时，集合的元素可以顺便访问，因为集合中的 节点没有访问顺序的限制，可以随意访问。所以我们可以先决定集合p 中各个节 点的访问顺序，接着当卡吊访问经过集合三中的元素时，我们就插入集合三中的 节点。基于以上事实，我们可以将l s p - p c 问题进行简化，我们可以暂时移去集 合和集合足中的元素，从而将问题简化为求解集合尸的问题。 我们可以按照以下步骤进行求解： 第1 步：确定集合尸； 第2 步：当访问经过集合三中的元素时，插入集合工中的元素，因为插入集 合三中的元素不会增加原有路径的长度； 第3 步，插入集合足中的元素。 现在我们已经给出了求解l s p - p c 问题方法的先行条件，接下来，为了阐述 的方便和便于理解，我们将分两步对l s p p c 问题进行介绍分析：单一约束和多 个约束。 1 、单一约束问题 如果l s p - p c 问题只有一个约束，那么我们就可以把它叫做关键链路径问题。 而且，按照上面介绍的方法，我们可以移走集合三和集合r 中的元素，而集合p 按照限制顺序进行访问，所以我们就可以用很简单的方法来求解， 第一步：找出集合尸，三和r ，同时找出节点即。令s 表示已访问节点的 访问顺序，刚开始时s = 0 0 ： 第二步：把集合尸中的元素按照给定的顺序放入集合s 中； 第三步：当访问经过集合中的元素时，将集合三中的元素放入集合s 中； 第四步：当访问完节点r p 后，把集合r 中的元素放入集合s 中。 最后我们就得到了单一约束问题的解。下面我们给出一个单一约束的问题的 例子，其简图如下： 铂垄接：3 7 一s 一9 4 6 图2 5 单一约束例子 按照上面的方法，最后求解的结果如下： ，ii| 1 l l | 丁 一 一1 上 1 1 一一1 一-1 一， d 2 468 1 01 21 4 图2 6 单一约束解法 以上是对单一约束条件进行讨论，接下来我们将对有多个约束条件的情况进 行讨论分析。 2 、多个约束条件 正如我们在上面讨论的那样，现在我们首先要确定集合p 中的元素。不像单 一约束那么简单，这里我们要调整各个约束的访问顺序，当我们访问完一个节点 时，下一步会有几个可行节点可以选择。而且最重要的是，这个问题拥有无后效 性的性质，这个发现让我们可以用动态规划的方法对其进行求解。 设k 个约束条件表示如下： 厶：p l l 寸a 2j j p l 厶：p 2 ljp 2 2 - - - - - p 2 厶 厶：仇l 专见2 专专魄 设集合( s ，b ) 表示中间状态过度状态，s 表示当前访问节点，弓表示当前访 问节点前所有已访问节点。在状态( 5 ，乓) 时的下一步是选择一个可行节点，假 设节点，符合条件，则状态从( s ，b ) 转移到状态( ，p ) ，然后进行下一步的选择。 设厂( s 只) 表示到达节点s 时访问耗费时间，其转移模型如下： 厂( s ，) = m 雠i n f ( ，c ) + c t ，s ) )( 2 - 1 ) 其中c ( t ，s ) 表示从节点，到节点s 所耗费的时间。所以函数表达式可以表示为： _ ，曼2 ，n 。 厂( ，尸n ) + c ( ，o ) ) ( 2 2 ) 接下来我们将会分析这个动态规划的计算复杂度。如上面假设，约束个数 的上限为k ，在这里是一个常量，我们以系数来对待。当处于状态( s ，只) 时，节 点s 的所有选择最大的可能为刀，最坏的情况是每个节点最多有k 个元素，所以 它的计算负责度为o ( n r + 1 ) 2 2 ，由于k 已知，所以在多项式时间内是可解的。 2 3 有时间窗口限制的线性往返问题 在某些情况下，根本不存在明显的前后顺序限制，而只有时间约束在起作用。 根据对以往论文的研究发现，还没有论文对l s p t w 问题的复杂性进行分析过。 在这篇论文里，我们将会给出l s p - t w 是n p - h a r d 问题的证明，同时给出一个有 效的解法。为了使证明简单易懂，我们将会重新描述这个问题。 如下图所示，在一条直线上，分布着不同的节点，而每个节点都有一个服务 时间窗口，最早开始时间和最迟开始时间，而访问的要求就是在满足时间窗口的 约束条件下，实现所走路径最短 2 2 。 圜 3 - 5l 缶2 - 41 1 - 1 31 2 1 31 5 _ 1 9 i o i 2 4 68 1 0 1 21 4 4 ，94 j 69 1 15 1 3 4 67 9 昏8 图2 7 时间窗口约束简图 既然对于初始节点0 而言，可能有时间窗口约束，也可能没有。在这篇论文 里，我们就假设开始节点也存在时间窗口的约束 2 3 。如果有需要，我们将放松 这个假设约束。如果存在可行解的话，目的是去寻找一个最优解，使访问所耗费 的时间最d x 2 4 ；如果不存在的话，给出不存在可行解的证明。 接下来我们将对这个问题的复杂性给出证明： 原理1 ：l s p - t w 问题是一个强n p c o m p l e t e 问题，甚至无法找到一个可行 2 1 的解法。 证明：首先，我们引入强n p - c o m p l e t e 的3 - p a r t i t i o n 问题，给定正整数n ， b 和，= 1 ，2 ，3 刀) ，同时存在正整数量，岛，使兰墨= n b ，其中 焉 。对任意的f ，集合，是否能够被