# Competitive Analysis of Algorithms for an Online Distribution Problem
## 1 Introduction  
Online problems are optimization problems in which the instance is revealed in an online manner and the solution is produced online. We study an online distribution problem where transportation prices are revealed over time. The producer has to accept one of these prices in order to send a load to a customer. The decision is taken on the basis of the transportation prices revealed so far. Only the range in which the transportation prices will fall is known, and the unit penalty cost must be paid whenever the offered price is not accepted. The latter cost may be the cost of obtaining a new quote, the penalty for a late delivery, the inventory cost the company has to pay to store the load for a certain time, or a combination of these costs. This penalty cost is constant from one period to the next. This problem has interesting real-world applications. In the last few years, transportation quotes have been easily obtainable from professional websites. For example, please refer to Shiply (www.shiply.com) or to Freightquote (www.freightquote.com). After providing the data concerning the load (origin, destination, type of products, weight and volume), transportation prices are obtained from transportation companies. At the end of the first time period, a decision must be made: to accept or to reject the minimum offered price without any information on the prices that will be observed in the future. These steps are repeated until a price is accepted. Note that the prices provided by thetransportation companies over time do not follow any trend because they mainly depend on the availability of other requests from close enough origins and destinations. For this problem, we design _online algorithms_, i.e., algorithms that make irrevocable decisions without full knowledge of the problem instance. The decision makers have full knowledge of the past, but no (or just partial) knowledge of the future. To evaluate their performance, [PERSON] et al. [1] suggested that these algorithms be compared with optimal offline algorithms. Moreover, [PERSON] et al. [2] introduced the concept of a _competitive ratio_. An online algorithm ALG is _\(c\)-competitive_ (with \(c\geq 1\)) if, given any problem instance \(I\), the cost \(ALG(I)\) of the solution given by the online algorithm ALG is no more than \(c\) times the cost \(OPT(I)\) of an optimal offline algorithm that knows the entire sequence of transportation prices in advance:  
\[\frac{ALG(I)}{OPT(I)}\leq c,\text{ for any problem instance }I.\]  
The smallest \(c\) such that \(ALG(I)\leq cOPT(I)\) is called the _competitive ratio_ of ALG. For the sake of simplicity, in the following, we will omit the reference to \(I\). The availability of the competitive ratio provides a guarantee for the worst-case performance of the online algorithm with respect to the optimal solution of the offline problem, where all information is already available at the beginning, before the first decision is made. The competitive ratio is also interesting from a managerial point of view, because the producer knows that, by using the online algorithm, the total cost they will pay over the time horizon will be at most \(c\) times the cost of the offline problem. If several online algorithms are available, the one with the smallest competitive ratio should be used to achieve the best possible worst-case performance guarantee. We refer to [PERSON] and [PERSON] [3] and to [PERSON] and [PERSON] [4] for a comprehensive description of online algorithms and competitive analyses, to [PERSON] [5] for a survey on online algorithms, and to [PERSON] and [PERSON] [6] for a survey of online vehicle routing problems. Recent contributions have been presented by [PERSON] et al. [7] for an online machine minimization problem; [PERSON] et al. [8] for online knapsack problems; [PERSON] et al. [9] for the online \(k\)-Canadian traveller problem; [PERSON] et al. [10; 11], [PERSON] and [PERSON] [12], [PERSON] et al. [13], and [PERSON] et al. [14] for online scheduling problems; [PERSON] et al.