基于約束的餐廳臺位管理外文翻譯譯文（節(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>　　基于約束的餐廳臺位管理</p><p>　　Alfio Vidotto，Kenneth N. grown，J. Christopher Beck</p><p><b>　　摘要</b></p><p>　　餐廳臺位管理在餐廳盈利和客戶體驗兩方面起著關(guān)鍵作用。本文所要解決的是一個復(fù)雜的動態(tài)的組合

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、t;　　Fig.2.臨時面對的問題(左)；和一個應(yīng)對的方案（右）。</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. 對Fig.

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