帶時(shí)間窗約束的接送調(diào)度與人力規(guī)劃問(wèn)題的啟發(fā)式算法研究.pdf

1、隨著經(jīng)濟(jì)和技術(shù)的迅速發(fā)展、網(wǎng)絡(luò)購(gòu)物等的逐漸流行,運(yùn)輸服務(wù)的作用日益顯著,成為商業(yè)和日常生活的基礎(chǔ)環(huán)節(jié)。車輛路徑優(yōu)化問(wèn)題主要研究車輛路線的安排,以降低運(yùn)輸成本、節(jié)約費(fèi)用。同時(shí),該問(wèn)題還會(huì)涉及員工排班問(wèn)題。良好的排班,可以調(diào)動(dòng)員工的積極性,創(chuàng)造良好的工作氛圍,從而提高工作效率。在過(guò)去的半個(gè)多世紀(jì)中,車輛路徑問(wèn)題和員工排班問(wèn)題被分開研究,并取得了豐富的研究成果。最近為了使研究更加貼近實(shí)際應(yīng)用,越來(lái)越多的學(xué)者開始將這兩個(gè)問(wèn)題結(jié)合起來(lái)進(jìn)行研究。<

2、br>　　 本文主要解決香港公立醫(yī)院的非緊急救護(hù)車載送服務(wù)問(wèn)題。它主要為殘疾和年老的病人提供診所和居住地之間的接送服務(wù)。該實(shí)際問(wèn)題不僅要求為救護(hù)車設(shè)計(jì)路線,而且需要為員工排班。這兩個(gè)問(wèn)題均屬于NP-難問(wèn)題,其混合問(wèn)題使得研究與現(xiàn)實(shí)更加緊密地聯(lián)系起來(lái),而且是一個(gè)更加復(fù)雜的優(yōu)化問(wèn)題。一個(gè)合理的解決方案需要滿足一系列的約束條件,比如:服務(wù)時(shí)間窗、容量限制、最大旅行時(shí)間、車輛消毒和人員安排等。該問(wèn)題的研究有重要的應(yīng)用價(jià)值,它有利于提高醫(yī)院的服

3、務(wù)質(zhì)量,而且該模型適用于很多實(shí)際應(yīng)用。
　　 本文采用迭代局部搜索與變鄰域下降搜索的混合算法來(lái)解決該實(shí)際問(wèn)題。為了處理最大旅行時(shí)間限制,提出一種快速的方法對(duì)路徑進(jìn)行時(shí)間壓縮,同時(shí)應(yīng)用一個(gè)貪心啟發(fā)式策略來(lái)快速地求解員工排班約束。為了減少算法的運(yùn)行時(shí)間,本文依據(jù)該問(wèn)題的特點(diǎn),提出了一些策略來(lái)減小搜索空間。為了顯示該算法的性能,模擬退火算法框架被用來(lái)做對(duì)比實(shí)驗(yàn)。另外,本文給出的算法被用于求解另一個(gè)車輛路徑問(wèn)題,并與文獻(xiàn)中的算法進(jìn)行結(jié)果