南台科技大学
工业管研究所 硕士学位文
线上型派系统应用於线货运业辆派遣 作业之研究
The Development of A On-Line System in Solving the Vehicle Dispatching Problem of Fixed-Route Trucking Carriers
研 究 生:欧阳昆
指导教授:施武荣 博士
中华民国九十七月
博硕士文授权书
本授权书所授权之文为本人在南台科技大学 组 文. 文名称:线上型派系统应用於线货运业辆派遣作业之研究 本人具有著作财产权之文全文资(含纸本及电子档),授予下单位:
同意即公开 同意一后公开 □ ■ 单 本人毕业学校图书 位
工业管研究所 学期取得 硕
系(所) 士学位之
九十五
学第
二
(上述勾选一后公开者,请於缴交纸本文给本校图书时特别声明,否则一以即公开处)
同意公开 □
同意公开 ■
单
位
国家图书(同意公开,请於上传登之后将所印出的
授权书送交所属系所统一寄给国图;纸本文则一定要送 交教务处注册组汇转国图,是否同意公开全文)
政院国家科学委员会科学技术资中心 □ ■
(授权国科会科学技术资中心者,请个别再寄文一本 至台市(106-36)和平东二段 106 号 1702 室) .
为学术研究之目的以各种方法重制得限地域,时间与次以微缩,光碟或其他各 种位化方式重制后散布发或上载网站,藉由网传输,提供者基於个人非营 性质之线上检,阅览,下载或印,惟每人以一份为限.
□上文为授权人向经济部智慧财产局申请专之附件或相关文件之一 (专申请案号: 开或上载网.
(勾选此项者,请於缴交纸本文给本校图书时特别声明,否则一以即公开处)
),请於______月___日后再将上文公
-------------------------------------------------------------------------------------------------------------------上述授权内容均无须订让与及授权约书.依本授权之发权为非专属性发权 .依本授权所为之收,重制,发及学术研发用均为无偿.上述之位未 钩选,本人同意视同授权. 指导教授姓名:施武荣 研究生签名: 学 电 地 日 号:M9450205 话:06-2533131 址:台南县永康市南台街 1 号 期:中华民国 九十 七 月 七 日 (亲笔正楷) (务必填写) E-mail:M9450205@webmail.edu.tw
摘要
随著企业国际化之趋势,许多商品的销通产生改革,有别於传统的销 通需透过层层转运,目前的商品配送已经逐渐走向「少,多样化,高效」 的趋势,故线货运业如何提升竞争,低运输成本,遂成为重要目标之一. 本研究针对个案公司实际况考,探讨多场站辆途程问题,其特性包含辆 的承载,派,线的规划,时窗限制等.由於此问题是具有多重限制的 NP-hard 问题,要求取最佳解,其计算时间会随著场站的增加呈现指的成 长,因此问题规模大时求取最佳解往往相当费时,故通常要求尽可能接近最佳解 就可.为兼顾实务上之求解速与品质,本研究采用启发式解法求解近似最佳 解.本研究运用混合基因演算法求解多场站辆途程问题,协助个案公司能快 速地处派问题.此演算法先探讨如何以先分群再指派场站,然后用时间导 向最邻近搜寻法建构初始解以快速求得可解,接续运用基因演算法的寻优特性 改善求解品质,并让求得之可解能跳脱区域最佳解的限制,以增加全域最佳 解的机会.本研究并依此建构一线上型辆派遣运作系统,期望在此系统下能提 高求解效及较佳搜寻线,并以传统启发使演算法比较,经测试结果证明,本 研究所提出之混合基因演算法,确实具有较佳求解能,使整体配送成本低, 效增大.
关键词:辆途程问题,具时窗限制多场站辆途程,基因演算法,时间导向最 邻近搜寻法
iv
Abstract
With the business trends toward the globalization, the marketing channels, differed from the traditional ways, have reformed. Today, the way of product delivery has been toward the trend of wide variety, few amount and high efficiency. In this research, an empirical vehicle routing case is addressed for a transportation company. In the case, the research considers the characteristics of vehicle routing, quantity dispatch, routes arrangement, and Time-window constraints in order to reduce the transportation cost. A hybrid heuristic algorithm was used in solving this practical problem. The developed algorithm firstly employed the Nearest-Neighbor search heuristic to search the feasible solution based on the constraints of Time-window and loading capacity. By the virtue of Genetic Algorithm to improve the quality of the initial solutions, the developed algorithm then enables the solutions to jump out the local optimization and gain a better performance in product delivering. A web-based vehicle routing system which is integrated with the developed algorithm is also developed to assist engineering in configuring the appropriate vehicle routing and dispatching operations. The result has shown that the developed hybrid genetic algorithm method can actually achieve a better solution capability and reduce the transportation cost for the company.

下一页