{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:09:37Z","timestamp":1760144977597,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T00:00:00Z","timestamp":1717372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We study an online distribution problem in which a producer has to send a load from an origin to a destination. At each time period before the deadline, they ask for transportation price quotes and have to decide to either accept or not accept the minimum offered price. If this price is not accepted, they have to pay a penalty cost, which may be the cost to ask for new quotes, the penalty cost for a late delivery, or the inventory cost to store the load for a certain duration. The aim is to minimize the sum of the transportation and the penalty costs. This problem has interesting real-world applications, given that transportation quotes can be obtained from professional websites nowadays. We show that the classical online algorithm used to solve the well-known Secretary problem is not able to provide, on average, effective solutions to our problem, given the trade-off between the transportation and the penalty costs. Therefore, we design two classes of online algorithms. The first class is based on a given time of acceptance, while the second is based on a given threshold price. We formally prove the competitive ratio of each algorithm, i.e., the worst-case performance of the online algorithm with respect to the optimal solution of the offline problem, in which all transportation prices are known at the beginning, rather than being revealed over time. The computational results show the algorithms\u2019 performance on average and in the worst-case scenario when the transportation prices are generated on the basis of given probability distributions.<\/jats:p>","DOI":"10.3390\/a17060237","type":"journal-article","created":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T05:58:00Z","timestamp":1717394280000},"page":"237","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Competitive Analysis of Algorithms for an Online Distribution Problem"],"prefix":"10.3390","volume":"17","author":[{"given":"Alessandro","family":"Barba","sequence":"first","affiliation":[{"name":"Department of Economics and Management, University of Brescia, 25121 Brescia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Bertazzi","sequence":"additional","affiliation":[{"name":"Department of Economics and Management, University of Brescia, 25121 Brescia, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5270-6094","authenticated-orcid":false,"given":"Bruce L.","family":"Golden","sequence":"additional","affiliation":[{"name":"Robert H. Smith School of Business, University of Maryland, College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","article-title":"Amortized efficiency of list update and paging rules","volume":"28","author":"Sleator","year":"1985","journal-title":"Commun. ACM"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF01762111","article-title":"Competitive snoopy caching","volume":"3","author":"Karlin","year":"1988","journal-title":"Algorithmica"},{"key":"ref_3","unstructured":"Borodin, A., and El-Yaniv, R. (2005). Online Computation and Competitive Analysis, Cambridge University Press."},{"key":"ref_4","unstructured":"Hentenryck, P.V., and Bent, R. (2009). Online Stochastic Combinatorial Optimization, The MIT Press."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10107-003-0436-0","article-title":"Online algorithms: A survey","volume":"97","author":"Albers","year":"2003","journal-title":"Math. Program."},{"key":"ref_6","unstructured":"Jaillet, P., and Wagner, M.R. (2008). The Vehicle Routing Problem: Latest Advances and New Challenges, Springer."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2057","DOI":"10.1137\/17M116032X","article-title":"An O(log m)-Competitive Algorithm for Online Machine Minimization","volume":"47","author":"Chen","year":"2018","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Ma, W., Simchi-Levi, D., and Zhao, J. (2019). A Competitive Analysis of Online Knapsack Problems with Unit Density. arXiv.","DOI":"10.2139\/ssrn.3423199"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1086","DOI":"10.1007\/s10878-019-00438-6","article-title":"Multiple Canadians on the road: Minimizing the distance competitive ratio","volume":"38","author":"Desmarchelier","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/s11590-017-1113-1","article-title":"Online batch scheduling with kind release times and incompatible families to minimize makespan","volume":"12","author":"Li","year":"2018","journal-title":"Optim. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/s11590-016-1096-3","article-title":"Uniform parallel machine scheduling problems with fixed machine cost","volume":"12","author":"Li","year":"2018","journal-title":"Optim. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/s11590-017-1191-0","article-title":"Online c-benevolent job scheduling on multiple machines","volume":"12","author":"Yu","year":"2018","journal-title":"Optim. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s11590-017-1198-6","article-title":"On the on-line maintenance scheduling problem","volume":"12","author":"Shamsaei","year":"2018","journal-title":"Optim. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1663","DOI":"10.1007\/s11590-018-01384-8","article-title":"Optimal online algorithms for MapReduce scheduling on two uniform machines","volume":"13","author":"Jiang","year":"2019","journal-title":"Optim. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.trb.2021.05.017","article-title":"An online optimization approach to post-disaster road restoration","volume":"150","author":"Akbari","year":"2021","journal-title":"Transp. Res. Part Methodol."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1016\/j.ejor.2021.10.036","article-title":"Online crowdsourced truck delivery using historical information","volume":"301","author":"Zhang","year":"2022","journal-title":"Eur. J. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"106314","DOI":"10.1016\/j.cor.2023.106314","article-title":"Online optimisation for ambulance routing in disaster response with partial or no information on victim conditions","volume":"159","author":"Shiri","year":"2023","journal-title":"Comput. Oper. Res."},{"key":"ref_18","first-page":"653","article-title":"The Secretary Problem with Predictions","volume":"49","author":"Fujii","year":"2023","journal-title":"Math. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1287\/opre.2022.2419","article-title":"Tight guarantees for static threshold policies in the prophet secretary problem","volume":"71","author":"Arnosti","year":"2023","journal-title":"Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Salem, J., and Gupta, S. (2023). Secretary problems with biased evaluations using partial ordinal information. Manag. Sci.","DOI":"10.1287\/mnsc.2023.4926"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Shiri, D., Akbari, V., and Salman, F.S. (2024). Online algorithms for ambulance routing in disaster response with time-varying victim conditions. OR Spectr., 1\u201335.","DOI":"10.1007\/s00291-024-00744-4"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Chen, Z.L. (2024). Online Integrated Production and Distribution Scheduling: Review and Extensions. INFORMS J. Comput.","DOI":"10.1287\/ijoc.2022.0305"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/3374857.3374871","article-title":"SIGACT News Online Algorithms Column 35: 2019 in review","volume":"50","author":"Schmitt","year":"2019","journal-title":"ACM SIGACT News"},{"key":"ref_24","first-page":"89","article-title":"SIGACT News Online Algorithms Column 36: 2020 in review","volume":"51","author":"Schmitt","year":"2021","journal-title":"ACM SIGACT News"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/3510382.3510396","article-title":"SIGACT news online algorithms column 38: 2021 in review","volume":"52","author":"Hohne","year":"2022","journal-title":"ACM SIGACT News"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1145\/3639528.3639538","article-title":"SIGACT News Online Algorithms Column 41: 2023 in review","volume":"54","author":"Amouzandeh","year":"2024","journal-title":"ACM SIGACT News"},{"key":"ref_27","first-page":"282","article-title":"Who solved the secretary problem?","volume":"4","author":"Ferguson","year":"1989","journal-title":"Stat. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/3331033.3331039","article-title":"Recent developments in prophet inequalities","volume":"17","author":"Correa","year":"2019","journal-title":"ACM SIGecom Exch."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s00453-001-0003-0","article-title":"Optimal search and one-way trading online algorithms","volume":"30","author":"Fiat","year":"2001","journal-title":"Algorithmica"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/237\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:52:55Z","timestamp":1760107975000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/6\/237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,3]]},"references-count":29,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["a17060237"],"URL":"https:\/\/doi.org\/10.3390\/a17060237","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,6,3]]}}}