We introduce the dynamic multiperiod routing problem to capture the key characteristic of situations such as the one described earlier. More specifically, at the beginning of each time period a set of customers requires a service to be fulfilled either that time period or the next. Thus, in each time period there are customers which need to be served, namely the customers that have been postponed the previous time period, and customers whose service may be postponed, namely the customers that have arrived this time period. The objectiveoftheproblemistominimizethetotaldistancetraveled during the planning horizon. To be able to focus first and foremost on the dynamic nature of demand, i.e., orders being revealed over time, we keep the routing component of the problem as simple as possible by not including capacity considerations, i.e., by assuming a single vehicle with unlimited capacity.
We present a few simple algorithms, ones which naturally arise in practice, and analyze these algorithms by studying their competitive ratio. We study these algorithms in different settings by varying the length of the planning horizon (two periods, more than two periods) and the locations of the customers (on the real line, in the Euclidean plane). More specifically, we analyze the performance of Algorithm IMMEDIATE, which always serves customers as soon as possible, of Algorithm DELAY, which always serves customers as late as possible, and of Algorithm SMART, which ineachtimeperioddecideswhethertoservecustomersimmediately or whether to postpone service based on the routing cost of serving the set of customers that have to be served that time period and the routing cost of serving all the customers. Both Algorithm IMMEDIATE and Algorithm DELAY have a competitive ratio equal to 2. When we restrict the planning horizon to two time periods, Algorithm SMART is shown√
to be optimal with a competitive ratio of 2
for instances with customers located on the real line and with a competitive
ratio of 
for instances with customers located
in the Euclidean plane. The competitive ratio of SMART increases and the
algorithm is no longer optimal when the number of time periods in the planning
horizon is greater than or equal to three.
As mentioned above, the competitive ratio measures the price that has to be paid for the lack of information, and therefore provides insight in the sensitivity of algorithms to the availability of information. Even though the algorithms studiedinthispapermaynotbeuseddirectlyinpracticalsituations, the insights provided by their analysis may help in the design and implementation of effective practical heuristics.
The remainder of the paper is organized as follows. In Section 2 we formally introduce the dynamic multiperiod routingproblemanddiscussitskeycharacteristics.InSection 3 we analyze the performance of Algorithms IMMEDIATE, DELAY, and SMART, for the special case in which the planninghorizonconsistsofonlytwotimeperiods,andinSection 4wepresentresultsforthegeneralcaseinwhichtheplanning horizon has more than two time periods. Finally, in Section 5 we summarize our key findings and discuss future research directions.
We will now define the dynamic multiperiod routing problem (DMPRP) studied in this paper.
The planning horizon is divided into time periods of equal length. Orders from customers arrive at the beginning of each time period. Each order has to be fulfilled within two time periods after arrival. Consequently, at the beginning of each time period t, the distribution planner learns about a set of customers Ct|t+1 that can be served either in the current time period or in the next time period. A single vehicle is available at a central depot to make deliveries and fulfill orders in each timeperiod.Thevehiclehastoreturntothedepotattheendof each time period. The objective is to minimize the total travel cost, where we assume that the travel costs depend linearly on the distance.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.