[發(fā)明專利]降低PCARP問題中車輛數(shù)的任務(wù)日程安排方法及電子設(shè)備

有效

• 申請(qǐng)?zhí)枺?/td>: 202011150429.0
• 申請(qǐng)日: 2020-10-23
• 公開（公告）號(hào): CN112258048B
• 公開（公告）日: 2023-07-21
• 發(fā)明（設(shè)計(jì)）人: 張玉州;張海奇;梅一
• 申請(qǐng)（專利權(quán)）人: 安慶師范大學(xué)
• 主分類號(hào): G06Q10/0631
• 分類號(hào): G06Q10/0631;G06Q10/109;G06F16/901
• 代理公司: 溫州市品創(chuàng)專利商標(biāo)代理事務(wù)所(普通合伙) 33247
• 代理人: 吳海云

本發(fā)明涉及車輛路由技術(shù)領(lǐng)域，具體涉及一種降低PCARP問題中車輛數(shù)的任務(wù)日程安排方法及電子設(shè)備，包括以下步驟：S1將所有固定型任務(wù)分配依據(jù)日程安排到相應(yīng)的日程里；S2在可重分配任務(wù)集合中選取符合要求的任務(wù)及服務(wù)日程安排；S3根據(jù)S2的選取更新各日程的需求量，同時(shí)更新可重分配任務(wù)集合并繼續(xù)任務(wù)分配；S4計(jì)算各日程中所需要的車輛數(shù)和整個(gè)問題安排中所需車輛數(shù)；S5得到問題所需車輛數(shù)為單個(gè)日程所需車輛數(shù)的最大值，合理安排任務(wù)到相應(yīng)日程中。本發(fā)明通過服務(wù)頻率的劃分，任務(wù)歸類為固定型和多選分配型。首先安排固定性，然后根據(jù)各日程中的任務(wù)需求量，合理安排任務(wù)到相應(yīng)日程中，以使得各日程中的任務(wù)需求量均勻分配。

技術(shù)領(lǐng)域

本發(fā)明涉及車輛路由技術(shù)領(lǐng)域，具體涉及一種降低PCARP問題中車輛數(shù)的任務(wù)日程安排方法及電子設(shè)備。

背景技術(shù)

限量弧路由問題(Capacitated?Arc?Routing?Problem，CARP)，首先由Golden?andWong提出，其有著廣泛的實(shí)際應(yīng)用背景，如郵件投遞、街道清掃、垃圾回收、社區(qū)網(wǎng)絡(luò)設(shè)計(jì)以及校園巴士等，所以CARP的研究具有廣闊的實(shí)際應(yīng)用價(jià)值。如今，這些與運(yùn)輸后勤密切相關(guān)的應(yīng)用問題已成為工業(yè)界內(nèi)最為重要的一環(huán)。例如，在冬季，為了防止街道結(jié)冰從而引發(fā)交通事故，英國(guó)每年消耗在給相關(guān)街道撒鹽以預(yù)防其結(jié)冰的費(fèi)用高達(dá)數(shù)百萬(wàn)英鎊。CARP問題旨在研究對(duì)具有復(fù)雜結(jié)構(gòu)的交通圖，如何科學(xué)地進(jìn)行車輛調(diào)度、合理地規(guī)劃路徑，在所有對(duì)象均被服務(wù)的前提下，實(shí)現(xiàn)車輛服務(wù)費(fèi)用的最小化。

CARP可描述為在無(wú)向連通圖G＝(V，E)上，尋找包含所有特殊邊(存在服務(wù)需求邊，亦稱為任務(wù))的路徑集合，使得駐留在中心點(diǎn)的車輛能夠以最小的費(fèi)用服務(wù)這些路徑，且路徑上的任務(wù)總需求量不得超過對(duì)應(yīng)服務(wù)車輛的容量，這里V和E分別表示頂點(diǎn)集和邊集，存在服務(wù)需求的邊稱為任務(wù)。顯然，CARP是一類典型的組合優(yōu)化問題，且為NP-hard。

近年來，CARP受到了越來越多研究者的關(guān)注，并取得了一系列的研究成果，然而這些研究往往針對(duì)基本CARP，而實(shí)際生活中許多問題則是其模型的擴(kuò)展，如周期性CARP(Periodic?Capacitated?Arc?Routing?Problem,PCARP)、多中心CARP等。例如，在城市垃圾回收問題中，有的區(qū)域垃圾量大，需要每天回收，而有的區(qū)域則垃圾量少，可周期性間隔處理。周期性CARP則應(yīng)對(duì)此類情況而提出，其可描述為根據(jù)任務(wù)的服務(wù)需求量，在某一周期內(nèi)設(shè)定其服務(wù)頻率，合理安排服務(wù)日程，從而降低車輛的服務(wù)費(fèi)用。相對(duì)于基本CARP，PCARP的目標(biāo)有兩個(gè)：(1)車輛數(shù)最少；(2)車輛費(fèi)用最少。

對(duì)于基本CARP而言，通常的目標(biāo)為車輛費(fèi)用的最少化，包括車輛的行駛耗費(fèi)、任務(wù)需求的服務(wù)費(fèi)用。然而，對(duì)于PCARP，相關(guān)部門更關(guān)注的是車輛數(shù)，因?yàn)橐粋€(gè)周期內(nèi)有若干服務(wù)日程，較差的任務(wù)日程安排會(huì)導(dǎo)致某一日程中的任務(wù)堆聚，從而服務(wù)車輛數(shù)增加。車輛的投資費(fèi)用高，且若某一日程的任務(wù)大量堆聚，導(dǎo)致的另一個(gè)結(jié)果是存在某些車輛在其他日程中閑置。所以，PCARP的目標(biāo)兩個(gè)目標(biāo)中，車輛數(shù)的最優(yōu)化為首要目標(biāo)。

降低車輛數(shù)，最有效的途徑是將一個(gè)周期內(nèi)的任務(wù)需求量均勻地分配至各日程中。然而，這是很困難的問題，因?yàn)閷?duì)于PCARP，存在眾多需要服務(wù)的任務(wù)，而任意任務(wù)又會(huì)存在若干服務(wù)日程安排。所以，對(duì)所有任務(wù)選擇合適的日程安排，使得任務(wù)需求量的均勻分布，然后進(jìn)行確定車輛數(shù)的過程是非常復(fù)雜的。

關(guān)于PCARP，有眾多學(xué)者提出了解決方法，如Lacomme等提出的進(jìn)化方法EA，Chu等提出的散射搜索方法SS，Kansou等提出的蟻群系統(tǒng)方法ACS，Mei等提出的路徑合并方法MARM以及Zhang等提出的路徑分解方法MARD等。這些方法通常是隨機(jī)地生成問題的初始解決方案，即任務(wù)的日程安排隨機(jī)地產(chǎn)生，在后續(xù)的處理過程中關(guān)注車輛數(shù)的減少。如此，會(huì)降低問題的解決效率，影響最終問題解決方案的質(zhì)量。