In case of a finite planning horizon, i.e., consisting of a finite number of time periods t = 1,2,...,T, we assume that every order has to be fulfilled within the planning horizon, i.e., orders that arrive in the last time period have to be served in that time period, and that the system did not necessarily start empty. We denote the set of customers already in the system at the start of the planning horizon, which have to be served in the first time period, by C1 and we denote the set of customers arriving in the last time period, which have to be served in the last period, by CT.
When making decisions at the beginning of the first time period, the decision maker knows the customers in C1 and in C1|2. At the beginning of time period t, 2 ≤ t ≤ T − 1, the decision maker knows the customers in Ct−1|t and Ct|t+1 and knows which customers of the set Ct−1|t have been served at time t − 1, but has no knowledge of the customers in Cs|s+1
for s = t + 1,...,T − 1 and in CT. Obviously, the decision maker has also knowledge of the customers in Cs−1|s, for s < t, but these customers have already been served and do not influence the decision at time t. At time T the customers in CT−1|T which have not been served at time T − 1 need to be served together with the customers in CT.
Ingeneral,thedecisionmakerhastomakedecisionsbased onpartialinformation.Considerthesituationatthebeginning of time period t. A set of customers which have to be served in time period t (because they were postponed in time period t − 1) and a set of customers which may be served at time period t or postponed to time period t + 1 (because they just arrived) are known. Clearly, if the newly arrived customers are located close to the customers that have to be served, it may be advantageous to serve these customers in time period t too. On the other hand, if the newly arrived customers are located far from the customers that have to be served, it may be advantageous to postpone their service in the hope that in the next time period their service can be combined with the customers that arrive in that time period.
It is common to analyze the performance of algorithms for optimization problems with incomplete information by studying their competitive ratio [16]. Let z(A,I) denote the value produced by algorithm A on instance I, and let z∗(I) denote the value produced by an optimal off-line algorithm, i.e., an algorithm with access to perfect information, on instance I. The competitive ratio rA of algorithm A is defined as
z(A,I) rA = max .
I z∗(I)
An on-line algorithm A is optimal if no other algorithm A has a competitive ratio rA < rA. Throughout the paper we willadoptthesameapproachforstudyingtheperformanceof algorithms for the DMPRP and we calculate the competitive ratio of various algorithms bounding from above the ratio rA(I) = z(A,I)/z∗(I) for all instances I. Even with perfect information, or perfect hindsight, the DMPRP is NP-hard as it contains the TSP as a subproblem.
We start our analysis of the DMPRP by considering the special case in which the planning horizon has only two time periods, i.e., T = 2. We believe it is of interest to study this special case, because it already allows us to concentrate on the need to make decisions with only partial information.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.