基于約束的餐廳臺(tái)位管理外文翻譯譯文（節(jié)選）

1、<p><b>　　中文3060字</b></p><p>　　本文譯自：Alfio Vidotto, Kenneth N. Brown, J. Christopher Beck, Managing restaurant tables using constraints, Knowledge-Based Systems, Volume 20, Issue 2, March 2007

2、. </p><p>　　基于約束的餐廳臺(tái)位管理</p><p>　　Alfio Vidotto，Kenneth N. grown，J. Christopher Beck</p><p><b>　　摘要</b></p><p>　　餐廳臺(tái)位管理在餐廳盈利和客戶體驗(yàn)兩方面起著關(guān)鍵作用。本文所要解決的是一個(gè)復(fù)雜的動(dòng)態(tài)的組合

3、問(wèn)題——餐廳臺(tái)位配置。我們將展示如何在既定條件下，將有限的餐廳臺(tái)位擴(kuò)展生成靈活多變的餐廳臺(tái)位配置方案，使其能應(yīng)付不同顧客的不同要求。本文描述了一個(gè)可實(shí)現(xiàn)向用戶提供實(shí)時(shí)建議的系統(tǒng)，該系統(tǒng)目前正在一間餐廳中運(yùn)行。</p><p>　　關(guān)鍵詞：約束；變化；不確定性；餐廳管理 </p><p><b>　　1.引言</b></p><p>　　有效的餐

4、廳臺(tái)位管理在提高一間餐廳的盈利能力是至關(guān)重要的——無(wú)效的臺(tái)位管理意味著，該餐廳將要失去潛在的顧客，但過(guò)多訂單卻意味著顧客被擱置，他們會(huì)產(chǎn)生不滿意和受欺騙的感覺(jué)，不想再光顧這間餐廳。此外，客戶的行為是不確定的，臺(tái)位配置計(jì)劃相應(yīng)地應(yīng)該是靈活的，或者說(shuō)是能迅速地不斷改變的，以避免過(guò)多顧客被擱置。餐廳經(jīng)理面臨著一系列的問(wèn)題：最后的四人桌應(yīng)該提供給二人聚餐嗎？我們應(yīng)該預(yù)留一個(gè)常客的高級(jí)臺(tái)位多長(zhǎng)時(shí)間呢？在晚上8點(diǎn)后還可以提供一個(gè)四人聚餐的臺(tái)位嗎？如

5、果在晚上7點(diǎn)時(shí)沒(méi)有臺(tái)位，新訂單應(yīng)該安排在哪個(gè)時(shí)間呢？當(dāng)一個(gè)聚餐超過(guò)了預(yù)定的時(shí)間，我們可以重新分配聚餐順序以避免顧客被擱置嗎？當(dāng)聚餐被取消后，我們可以再接上后續(xù)的聚餐來(lái)空出另一個(gè)臺(tái)位？在計(jì)算機(jī)領(lǐng)域里，餐廳臺(tái)位管理是一個(gè)動(dòng)態(tài)的受約束的組合優(yōu)化問(wèn)題——餐廳必須在現(xiàn)實(shí)中管理訂單和處理突發(fā)事件下，最大限度地發(fā)揮臺(tái)位的效率。</p><p>　　在本文中，我們描述了一個(gè)解決餐廳臺(tái)位管理問(wèn)題的實(shí)施方案，幫助管理者回答上述問(wèn)題。

6、該解決方案在滿足既定的約束條件下，同時(shí)又提高了靈活性和穩(wěn)定性。我們描述的這個(gè)系統(tǒng)目前在一家餐館測(cè)試。在本文的其余部分安排如下：第2節(jié)介紹了餐廳臺(tái)位管理問(wèn)題的更多細(xì)節(jié)，并介紹了一間與本課題有關(guān)的餐廳。第3節(jié)分析滿足限定條件的必要元素。第4節(jié)提出了一個(gè)基本的約束模型和搜索算法。第5節(jié)調(diào)整這模型以提高靈活性，以進(jìn)一步搜索更靈活的計(jì)劃。而第6節(jié)通過(guò)我們的方法來(lái)找到一個(gè)穩(wěn)定的計(jì)劃。第7節(jié)展示我們實(shí)現(xiàn)的系統(tǒng)的用戶界面。最后，第8節(jié)描述了結(jié)論和今后的

7、工作。</p><p><b>　　2.餐廳臺(tái)位管理</b></p><p>　　Eco[1]是在道格拉斯科克城的一個(gè)有名的中等餐廳，每周都有非常高的客流量。它也是發(fā)生在2000年的第一個(gè)開創(chuàng)了利用計(jì)算機(jī)互聯(lián)網(wǎng)來(lái)解決這問(wèn)題的先例，即E-mail預(yù)訂。餐廳設(shè)有23桌，從2到8（圖1）大小不等。一些臺(tái)位的容量依賴于其他臺(tái)位的情況：例如，臺(tái)位2和臺(tái)位15都可以坐6個(gè)座位，但

8、當(dāng)其中一個(gè)臺(tái)位是由5或6個(gè)人就餐時(shí)，那么另一桌就容納最多不超過(guò)4個(gè)人。這些臺(tái)位也可以是這樣配置：例如，雙人桌21和22可以拼在一起來(lái)容納3-5個(gè)人用餐。利用合并的臺(tái)位來(lái)舉行聚會(huì)時(shí)，聚餐最多不能超過(guò)30人。這里有超過(guò)100種不同的可設(shè)計(jì)的臺(tái)位安排，因此這餐廳的容量范圍從85到94。在這餐廳的晚上聚會(huì)在下午4點(diǎn)開始，而最后的聚會(huì)只能舉行到晚上10:30。在這些條件下，餐廳旨在每個(gè)晚上接待190和210個(gè)顧客——現(xiàn)實(shí)卻非如此，造成這結(jié)果的原因

9、是臺(tái)位沒(méi)有被很好地被利用；更嚴(yán)重地是，廚房還被拉伸以便能及時(shí)提供食物。Eco的臺(tái)位管理，就像大多數(shù)的餐廳，要應(yīng)付兩個(gè)階段的問(wèn)題：預(yù)訂和現(xiàn)場(chǎng)管理.</p><p><b>　　圖1.餐廳的布局</b></p><p>　　在預(yù)訂階段，老板要與顧客商討聚餐開始時(shí)間以使顧客的要求得到滿足，同時(shí)要安排能夠?qū)崿F(xiàn)既定營(yíng)業(yè)額的臺(tái)位安排方案。通常情況下，老板將預(yù)留臺(tái)位來(lái)應(yīng)對(duì)各種預(yù)訂要

10、求，而這幾乎不會(huì)改變；當(dāng)一個(gè)請(qǐng)求不能被容納在預(yù)訂表中時(shí)，顧客必須被說(shuō)服接受其他時(shí)間，不然他們的請(qǐng)求將被拒絕。然而，利用就餐順序的再分配也可以容納這些新的請(qǐng)求，這也是可實(shí)現(xiàn)的。在某些情況下，為了保持一個(gè)既定的計(jì)劃，餐廳將刪除一個(gè)預(yù)定，或者建議另一個(gè)時(shí)間，哪怕仍有一個(gè)臺(tái)位是可用的。此外，老板必須根據(jù)訂單的特性（包括時(shí)間，星期幾，和聚會(huì)的性質(zhì)）估計(jì)預(yù)期的就餐時(shí)間。</p><p>　　在現(xiàn)場(chǎng)管理方面，情況就完全不同了。

11、到了夜晚餐廳按照既定的預(yù)訂表營(yíng)業(yè)?？蛻粢呀?jīng)被安排到既定的時(shí)間，此時(shí)餐廳的目標(biāo)是使顧客能在盡量不受擱置的情況下就坐。當(dāng)發(fā)生改變時(shí)樓層經(jīng)理就得修改餐廳臺(tái)位計(jì)劃，以及接受或拒絕“不速之客”——使臨時(shí)到達(dá)餐廳的客戶無(wú)須任何提前預(yù)訂。樓層管理中的問(wèn)題是每一個(gè)顧客的情況都是無(wú)法提前預(yù)知的——他們可能會(huì)遲到，可能無(wú)法來(lái)就餐，可能需要較長(zhǎng)時(shí)間也可能比預(yù)期的要短，可能會(huì)臨時(shí)改變他們就餐的地方大小，當(dāng)然他們可能認(rèn)為他們已經(jīng)提前訂單，其實(shí)沒(méi)人記錄他的訂單。此

12、時(shí)樓層經(jīng)理必須立即應(yīng)付這些問(wèn)題，在漫漫長(zhǎng)夜里滿足顧客所有的要求，使每一個(gè)顧客都滿意歸去。</p><p>　　我們預(yù)期的解決辦法是建造一個(gè)互動(dòng)的軟件工具，協(xié)助餐廳人員完成預(yù)訂和現(xiàn)場(chǎng)管理工作。我們的研究課題的目標(biāo)是測(cè)試在既定條件下能否提供多個(gè)關(guān)于這個(gè)多變的和不確定的問(wèn)題的解決方案。如果該研究是成功的，一個(gè)新的工具將被開發(fā)，并納入客戶關(guān)系管理軟件。</p><p><b>　　3.解

13、決約束問(wèn)題 </b></p><p>　　一個(gè)約束問(wèn)題（CSP）是由已預(yù)訂的聚會(huì)構(gòu)成：{X1，X2，...，Xn}，與之相應(yīng)需要的臺(tái)位：{D1，D2，…Dn}，和限定條件：{C1,C2,…,Cm}所構(gòu)成的。每個(gè)限定條件都是由聚會(huì)所需要的臺(tái)位和餐廳所擁有的臺(tái)位間的關(guān)系所構(gòu)成的數(shù)組。一種關(guān)系就是這個(gè)解決方案的一些或全部的等值，{Xi= vi，Xj= vj...}。CSP的解決方案就是一個(gè)完整的配置方案，即

14、所有聚會(huì)都得到安排，{X1= v1，X2= v2,,...，Xn= vn}，即滿足所有的條件。解決CSP問(wèn)題的標(biāo)準(zhǔn)方法是基于回溯搜索交錯(cuò)約束傳播。關(guān)于這方面的約束編程的內(nèi)容可在[2]，[3]調(diào)查的最近研究中找到。</p><p>　　在搜索中，已經(jīng)經(jīng)過(guò)測(cè)試過(guò)的臺(tái)位安排必須被指定為檢索算法的一部分，并且對(duì)搜索樹的大小起著一定的作用。可變排序搜索方法選擇當(dāng)前最少臺(tái)位或者是臺(tái)位多少與滿足條件的預(yù)訂聚會(huì)的最小比。在CSP

15、的一個(gè)例子中，對(duì)應(yīng)一個(gè)運(yùn)行方式的單個(gè)搜索在獨(dú)自運(yùn)行中會(huì)受困在錯(cuò)誤的搜索樹的區(qū)域。為了避免這種情況，隨機(jī)重新搜索已經(jīng)被采納[4]——作為單個(gè)搜索，如果在既定的時(shí)間下沒(méi)有找到運(yùn)行方式，搜索將再次啟動(dòng)。突破局限和值排序的過(guò)程是隨機(jī)完成的，所以每次重啟探索一條不同的道路。類似地，算法組合[5]交織成一組隨機(jī)化算法。該[6]搜索強(qiáng)度是通過(guò)合并多個(gè)變量和既定時(shí)間下重新啟動(dòng)的值排序啟發(fā)式來(lái)提高的。</p><p>　　在限定進(jìn)

16、程中，未分配變量的臺(tái)位將通過(guò)一個(gè)方法被刪除，即刪除這些不能出現(xiàn)在這個(gè)能改變現(xiàn)時(shí)的情況的解決方案中的變量。例如，如果我們有條件X<Y，且X和Y的域分別為{ 2，3，4，5}和{1，2，3，4}，這時(shí)，將4和5可以從X的域排除，以及將1和2從Y的域排除，因?yàn)檫@些值都不能滿足這個(gè)條件。減少域值相應(yīng)地也減少子樹中被探索的域大小。約束編程工具的成功很大一部分是由于高效域?yàn)V波算法進(jìn)行專門的限制;也就是[7]。</p><p

17、>　　動(dòng)態(tài)問(wèn)題就是解決正在執(zhí)行計(jì)劃時(shí)出現(xiàn)的問(wèn)題——例如，在調(diào)度中，一臺(tái)機(jī)器可以熄火了，或計(jì)劃執(zhí)行中可能會(huì)由于供應(yīng)的遲到采取行動(dòng)而造成延遲。動(dòng)態(tài)CSP[8]模式根據(jù)不同問(wèn)題而改變。這樣做的目的是為了以最小的成本去尋找新的解決方案，或使兩套解決方案之間的轉(zhuǎn)換成本最小。目前我們聚焦在這樣一個(gè)問(wèn)題，即我們是否有多個(gè)解決這些變化的模式。[9]和[10]都是將來(lái)事件的變化的原因：[9]搜索能力和擴(kuò)展范圍有限在可執(zhí)行方案樹中起著約束作用; [1

18、0]測(cè)出POS的可選擇方案中，然后選擇其中具有最小遺憾值的方案。 [11]搜索具有最佳穩(wěn)定性的解決方案。他們與原來(lái)的解決方案作對(duì)比，并反復(fù)檢查是否需要重新分配一個(gè)變量或者兩個(gè)變量等，來(lái)解決新的問(wèn)題。 [12]提出了特別的穩(wěn)定條件。某些方法為了避免不穩(wěn)定而提供穩(wěn)固的解決方案。在[13]排序問(wèn)題中，其解決方法是通過(guò)加入靈活活動(dòng)的持續(xù)時(shí)間來(lái)實(shí)現(xiàn)。更高級(jí)的方法[14]是在多變的情況下保證有既定的修復(fù)值供應(yīng)。</p><p&g

19、t;　　Fig.2.臨時(shí)面對(duì)的問(wèn)題(左)；和一個(gè)應(yīng)對(duì)的方案（右）。</p><p>　　變量:{P1,P2,P3,P4,P5}</p><p>　　域:D1={T1,T2,T3,T4},D2={T2,T4},D3={T2,T3,T4},D4={T1,T2,T3,T4},D5={T1,T2,T3,T4}</p><p><b>　　限制條件：</b&g

20、t;</p><p>　　C1. all different([P1,P2,P3])</p><p>　　C2. all different([P3,P4,P5])</p><p>　　C3. (P2==T2)=>(P1≠T3,P3T3)</p><p>　　C4. (P3≠T3)||(P2≠T4)</p>

21、<p>　　C5. 3+(P2==T2)≦4</p><p>　　C6. P1.size+P2.size+P3.size<=12</p><p>　　C7. P3.size+P4.size+P5.size<=12</p><p>　　C8. P4<P5</p><p>　　Fig.3. 對(duì)Fig.

22、2.問(wèn)題的CSP過(guò)程</p><p><b>　　4.解決具體的問(wèn)題</b></p><p><b>　?。裕?lt;/b></p><p><b>　　5.靈活性和優(yōu)化</b></p><p><b>　　（略）</b></p><p&g