O2O模式下的配送車輛實(shí)時(shí)取送貨路徑選擇問題

摘要： 伴隨020模式下外賣市場的迅猛發(fā)展,由此導(dǎo)致的最后3公里配送需求日益激增,外賣的配送時(shí)效受到了廣泛的關(guān)注.外賣的及時(shí)配送,即配送車輛的路徑選擇問題成為餐飲服務(wù)業(yè)重要的研究問題.針對020平臺外賣配送服務(wù)過程中,需求無法確定和配送車輛必須返回原點(diǎn)取貨的情形,提出了帶有取送貨的在線旅行商問題(traveling salesman problem, TSP).分析了該問題在正半軸和一般網(wǎng)絡(luò)上的下界,針對需求點(diǎn)僅在正半軸上的情形設(shè)計(jì)了TAIB算法,針對需求點(diǎn)在一般網(wǎng)絡(luò)上設(shè)計(jì)了IGNORE算法,并進(jìn)一步分析了兩個(gè)算法的競爭性能,結(jié)論可以為現(xiàn)實(shí)中外賣配送車輛的實(shí)時(shí)調(diào)度決策提供依據(jù).
With the rapid development of the take-away market under 020 mode, the demand for the delivery of the last 3 kilometers has been increasing rapidly. The delivery effectiveness has been received extensive attention. The timely delivery of take-away, which is the routing of delivery vehicles has become an important research issue in the catering service industry. In the takeaway delivery service under 020 platform, the release time of the requests are uncertain and the delivery vehicle must return to the origin to pick up the goods. This paper proposes online traveling salesman problem with pickup and delivery. We give the lower bounds of the problem, when metric space is positive half-line, TAIB algorithm is presented.For general metric space, IGNORE algorithm is presented, and competitive analysis is given for these two algorithms respectively. The results can provide a basis for the real-time scheduling in delivery.