New Lower Bound and Exact Method for the Continuous Berth Allocation Problem

上下界 数学优化 计算机科学 修剪 启发式 约束(计算机辅助设计) 周转时间 列生成 数学 几何学 农学 生物 操作系统 数学分析
作者
Zhou Xu,Chung‐Yee Lee
出处
期刊:Operations Research [Institute for Operations Research and the Management Sciences]
卷期号:66 (3): 778-798 被引量:27
标识
DOI:10.1287/opre.2017.1687
摘要

We study a continuous berth allocation problem, where incoming vessels need to be assigned a mooring time as well as a berth location on a quay. It is a crucial element in port planning to achieve quick turnaround time for vessels. To solve this problem, many solution methods have been developed in the literature. However, gaps between the best-known lower and upper bounds on its optimal solutions are far from close. In this paper, we propose new and more effective solution methods for this important problem. By introducing a novel relaxation of the problem, we have derived a new lower bound that can be computed efficiently in quadratic time. By incorporating this new lower bound with some new heuristic and pruning techniques, we have developed a new exact method, based on a branch-and-bound approach. To demonstrate general applicability of the proposed methods, we have extended them to a more complicated problem, where decisions on berth allocations are restricted by a quay crane constraint. Extensive computational results have shown that, compared with previous state-of-the-art methods, our new methods have significantly reduced gaps between the lower and upper bounds and have solved more and larger instances to optimality in significantly less time. We have also performed sensitivity tests to demonstrate how robust the new solutions are against uncertainties in particular input parameters. The online appendix is available at https://doi.org/10.1287/opre.2017.1687 .
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
刚刚
思源的应助被静默采纳,获得10
1秒前
Wynne的应助被業業采纳,获得20
1秒前
666完成签到,获得积分10
1秒前
大力的一斩完成签到,获得积分10
2秒前
3秒前
繁荣的瑛的应助被大胆听莲采纳,获得10
3秒前
4秒前
愉快之槐完成签到,获得积分10
4秒前
小蘑菇的应助被xx采纳,获得10
7秒前
7秒前
慕青的应助被完美的蜜蜂采纳,获得10
7秒前
7秒前
wg发布了新的文献求助10
7秒前
7秒前
张伟完成签到,获得积分20
7秒前
田様的应助被Aurora采纳,获得10
8秒前
余溪完成签到,获得积分10
9秒前
直率翠绿发布了新的文献求助10
10秒前
张冠黄戴发布了新的文献求助10
10秒前
cdercder的应助被皮卡丘采纳,获得10
11秒前
11秒前
13秒前
null的应助被王土豆采纳,获得10
13秒前
14秒前
14秒前
小蘑菇的应助被leo采纳,获得10
14秒前
15秒前
田様的应助被XIAOLI采纳,获得20
15秒前
15秒前
15秒前
杨宇康完成签到,获得积分10
15秒前
16秒前
18秒前
18秒前
19秒前
星辰大海的应助被生半夏采纳,获得10
19秒前
19秒前
及禾发布了新的文献求助10
19秒前
含糊的云朵完成签到 ,获得积分10
20秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
Sex, Aging, and Death in a Medieval Medical Compendium: Trinity College Cambridge MS R.14.52, Its Texts, Language, and Scribe 500
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
基于结构调控的功能化水诱导发电材料与器件研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8188221
求助须知:如何正确求助?哪些是违规求助? 9576025
关于积分的说明 21845049
捐赠科研通 7786165
什么是DOI,文献DOI怎么找? 3435226
关于科研通互助平台的介绍 2559559
邀请新用户注册赠送积分活动 2482157