中國(guó)郵遞員問(wèn)題奇偶點(diǎn)圖上作業(yè)法最優(yōu)標(biāo)準(zhǔn)的商榷

王邦兆 陳永清 王海軍 魏志祥

摘要：論文討論了關(guān)于中國(guó)郵遞員問(wèn)題的一種誤解，分析了產(chǎn)生誤解的原因，提出了解決中國(guó)郵遞員問(wèn)題的指派問(wèn)題模型。

Abstract： This paper discusses a misunderstanding about the Chinese Postman Problem， analyzes the causes of misunderstanding， and proposes a assignment problem model to solve the Chinese Postman Problem.

關(guān)鍵詞：中國(guó)郵遞員問(wèn)題;奇偶點(diǎn)圖上作業(yè)法;指派問(wèn)題

Key words： Chinese Postman Problem; odd-even-point graphical operation method; assignment problem

中圖分類(lèi)號(hào)：O157.5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2018）36-0258-02

1? 中國(guó)郵遞員問(wèn)題與圖上作業(yè)法

郵遞員每天從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問(wèn)題是他應(yīng)如何安排送信的路線可以使所走的總路程最短。這個(gè)問(wèn)題由中國(guó)學(xué)者管梅谷在1960年首先提出的，他給出了解法——“奇偶點(diǎn)圖上作業(yè)法”，被國(guó)際上統(tǒng)稱(chēng)為“中國(guó)郵遞員問(wèn)題”。用圖論的語(yǔ)言描述，給定一個(gè)連通圖G，每邊e有非負(fù)權(quán)），要求一條回路經(jīng)過(guò)每條邊至少一次，且滿足總權(quán)最小[2]。中國(guó)郵遞員問(wèn)題的研究受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，國(guó)外最早研究中國(guó)郵遞員問(wèn)題的是J.Edmonds，他把中國(guó)郵遞員問(wèn)題稱(chēng)為Chinese Postman Problem（簡(jiǎn)稱(chēng)CPP）。國(guó)內(nèi)研究中國(guó)郵遞員問(wèn)題的學(xué)者更多，產(chǎn)生了一批優(yōu)秀的成果。馮俊文[3]提出了中國(guó)郵遞員問(wèn)題的整數(shù)規(guī)劃模型，李念祖[4]提出了中國(guó)郵遞員問(wèn)題的完全最優(yōu)子圖算法，汪海森[5]等提出了中國(guó)郵遞員問(wèn)題的匹配算法，金毅[6]對(duì)中國(guó)郵遞員問(wèn)題進(jìn)行了數(shù)理分析。

奇偶點(diǎn)圖上作業(yè)法的基本思想：如果郵遞員負(fù)責(zé)投遞范圍的街道圖中沒(méi)有奇點(diǎn)，它就是歐拉圖，郵遞員只要經(jīng)過(guò)所有街道一次且僅一次，就能得到最短的路徑;如果街道圖中有奇點(diǎn)，將奇點(diǎn)兩兩配對(duì)，重復(fù)配對(duì)的兩個(gè)奇點(diǎn)間的一條鏈，就可以得到歐拉圖，如果重復(fù)的路徑的總長(zhǎng)度達(dá)到最短，就得到了最優(yōu)解。

2? 對(duì)奇偶點(diǎn)圖上作業(yè)法最優(yōu)標(biāo)準(zhǔn)的誤解及其原因分析

國(guó)內(nèi)許多教材都出現(xiàn)了一處嚴(yán)重錯(cuò)誤，以清華大學(xué)出版社的《運(yùn)籌學(xué)》[1]為例，該教材（PP279-280）提出的奇偶點(diǎn)圖上作業(yè)法的最優(yōu)性條件為：①在最優(yōu)方案中，圖的每一條邊上最多有一條重復(fù)邊;②在最優(yōu)方案中，圖中每個(gè)圈上的重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。這個(gè)最優(yōu)性條件顯然存在嚴(yán)重錯(cuò)誤。圖2和圖3都完全滿足上述最優(yōu)性條件，兩個(gè)方案的權(quán)重不一樣，顯然它們不會(huì)都是最優(yōu)方案，圖2的方案更優(yōu)。

通過(guò)圖2和圖3的對(duì)比可以發(fā)現(xiàn)，這個(gè)“最優(yōu)標(biāo)準(zhǔn)” 產(chǎn)生錯(cuò)誤的原因是命題的大前提錯(cuò)誤，也就是說(shuō)，這個(gè)命題正確的大前提是奇點(diǎn)的配對(duì)方式正確。圖1共有v2、v4、v6、v8四個(gè)奇點(diǎn)，只有將v4和v8配對(duì)、v2和v6配對(duì)，才有可能尋找到最優(yōu)方案，其它的兩種配對(duì)方式都無(wú)法得到最優(yōu)解。

3? 中國(guó)郵遞員問(wèn)題的指派問(wèn)題模型與算法設(shè)計(jì)

根據(jù)奇偶點(diǎn)圖上作業(yè)法的思想，首先應(yīng)該選擇正確的方式將所有奇點(diǎn)進(jìn)行配對(duì)，重復(fù)配對(duì)的各對(duì)奇點(diǎn)間的最短路，就能得到最優(yōu)方案。

解決最優(yōu)配對(duì)的辦法可以用Dijkstra算法和指派問(wèn)題的模型予以解決，具體算法如下（假設(shè)圖中共有n個(gè)奇點(diǎn)v1、v2、…、vn，n一定為偶數(shù)）：

①用Dijkstra算法求出圖中任意兩個(gè)奇點(diǎn)間的最短距離dij和最短路;

②構(gòu)建指派問(wèn)題的模型：

所以，將v2和v6配對(duì)、將v4和v8配對(duì)，重復(fù)配對(duì)的奇點(diǎn)間的最短路，即可得到圖2所示的最優(yōu)方案。

參考文獻(xiàn)：

[1]《運(yùn)籌學(xué)》教材編寫(xiě)組.運(yùn)籌學(xué)[M].三版.清華大學(xué)出版社，2005，6.

[2]管梅谷.關(guān)于中國(guó)郵遞員問(wèn)題研究和發(fā)展的歷史回顧[J].運(yùn)籌學(xué)學(xué)報(bào)，2015，9.

[3]馮俊文.中國(guó)郵遞員問(wèn)題的整數(shù)規(guī)劃模型[J].系統(tǒng)管理學(xué)報(bào)，2010，12.

[4]李念祖.關(guān)于中國(guó)郵遞員問(wèn)題的最優(yōu)完全子圖算法[J].上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，8.

[5]汪海森，林耿，卓彩娥.中國(guó)郵遞員問(wèn)題的匹配算法[J].長(zhǎng)江大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，9.

[6]金毅.對(duì)“中國(guó)郵遞員問(wèn)題”的數(shù)理分析[J].科技經(jīng)濟(jì)市場(chǎng)，2009（03）.