Heuristic algorithms for the online integrated optimisation of order picking and vehicle routing decisions

Abstract

Recent changes in the retailing landscape require companies to optimise their operations in order to stay competitive. In a business-to-consumer context, the widespread adoption of e-commerce is posing challenges for retailers. Due to fierce competition between companies, responding to customer orders as fast as possible has become essential to attract customers. In a business-to-business context, a reduction in lead times can be observed, requiring fast customer response times. In order to reduce the delivery delays, new optimisation strategies are required. In this dissertation, new strategies are proposed to optimise the order handling process, with a focus on the order picking and vehicle routing subprocesses. A first strategy is the use of online optimisation algorithms, allowing to quickly consider dynamically arriving orders during the operations. A second strategy is the use of integrated decision-making. Instead of solving interrelated planning problems separately, a solution for the combined planning problem is obtained, leading to large efficiency improvements. In this dissertation, multiple metaheuristic algorithms are developed for the considered optimisation problems. All algorithms are able to handle dynamic order arrivals and solve the problem in an integrated manner. First, we study how order picking operations can be scheduled efficiently in a dynamic, business-to-business setting. For this, a heuristic algorithm is developed, which considers the integration of order batching, picker routing and batch scheduling decisions and is able to account for dynamic order arrivals. A comparison to the current state-of-the-art highlights the strong performance of the proposed algorithm in a static context. Next, experiments in the online context show the benefit of anticipating on future order arrivals, in order to keep the customer service level high. Additionally, the benefits of receiving customer orders a bit more in advance are shown, indicating the complexity of handling very urgent orders as fast as possible. Second, in order to show the applicability of the proposed algorithm in practice, a real-life study is performed on real-life order data. The real-life study shows the benefits of using our metaheuristic algorithm compared to simpler heuristics as used in the current operational practice. Large efficiency gains are possible, leading to an improved service level and reduced costs. Moreover, a waiting strategy is proposed, allowing to postpone an order picker’s departure at the depot if his batch is not filled to its capacity. The use of this waiting strategy is shown to lead to improved operational efficiency. Finally, the combined optimisation problem of order picking and vehicle routing operations in a business-to-consumer setting is studied. By considering the order picking and vehicle routing decisions in an integrated manner, improved solutions can be obtained. Four metaheuristic algorithms are developed to solve the combined order picking and vehicle routing problem, considering the integration of order picking and vehicle routing decisions to a different extent. The results show the benefits of using more sophisticated algorithms that consider the interaction between picking and routing. By performing experiments considering different operating conditions, the difficulty of accommodating to stringent customer requests is highlighted. Combined, in all settings considered, for both order picking individually and order picking and vehicle routing combined, the results indicate large benefits of adopting algorithms that use integrated decision-making strategies, in theoretical as well as practical settings. The use of order anticipation and a waiting strategy are studied and shown to lead to improved results in the order picking problem. In the reallife case, the proposed metaheuristic algorithm leads to strong performance improvements compared to the current operational practice, allowing for large cost reductions without harming service levels. Finally, in the study on the integrated order picking and vehicle routing problem, insights are obtained into the challenges of same-day delivery operations in an e-commerce setting. In a next step, these findings can be used to develop more effective pricing strategies for the delivery fees, as delivery fees tailored to current operational situation may contribute to the efficiency of the order handling process.

Door recente evoluties in de retail zijn bedrijven genoodzaakt hun processen te optimaliseren om concurrentieel te blijven. De massale adoptie van online bestellen door consumenten cre¨eert uitdagingen voor retailers. Omwille van de sterke concurrentie tussen bedrijven, wordt het essentieel om klanten te overtuigen door hen een zo snel mogelijke levering te beloven. Ook bedrijfsklanten worden steeds veeleisender wat betreft hun geaccepteerde levertermijn. Om de levertermijnen naar zowel consumenten als zakelijke klanten te kunnen verkorten, zijn nieuwe optimalisatiestrategie¨en noodzakelijk. In deze doctoraatsthesis worden nieuwe strategie¨en voorgesteld om het orderbehandelingsproces te verbeteren. Dit overkoepelende proces kan opgedeeld worden in enerzijds order picking, waarbij de bestelde goederen verzameld worden in een magazijn, en anderzijds rittenplanning, waarbij de producten op de gewenste locatie worden geleverd. Een eerste vernieuwing is de introductie van dynamische optimalisatiealgoritmes. Deze dynamische algoritmes zijn in staat om op nieuwe klantenorders in te spelen die binnenkomen terwijl de orderbehandelingsprocessen actief zijn, dynamische orders genoemd, door deze snel op te nemen in de operationele planning zodat een zeer korte levertermijn mogelijk wordt. Een tweede vernieuwing schuilt in de algoritmes zelf. In plaats van de order picking en rittenplanning individueel te optimaliseren, kunnen deze ook als een overkoepelend probleem opgelost worden, waarbij de interactie tussen de verschillende activiteiten mee in rekening genomen wordt. Door deze problemen op zo’n ge¨ıntegreerde manier op te lossen, zijn grote effici¨entiewinsten mogelijk. In deze thesis worden verschillende metaheuristieken, een type algoritme, ontwikkeld voor de te bestuderen problemen. Alle ontwikkelde algoritmes zijn dynamisch en proberen de problemen op een ge¨ıntegreerde manier op te lossen. Om te beginnen bestuderen we hoe de order picking activiteiten effici¨ent gepland kunnen worden in een dynamische, business-to-business context. Hiervoor wordt een algoritme voorgesteld dat het picking probleem oplost door beslissingen in verband met order batching (het groeperen van orders in overkoepelende taken), picker routering (het bepalen van de route die een orderpicker aflegt binnen het magazijn) en batch planning (de beslissing over welke orderpicker welke batch zal behandelen en in welke volgorde) op een ge¨ıntegreerde wijze te nemen, en dit binnen een dynamische context. Eerst wordt in een statische context, waarbij alle orders aan het begin van de planningsperiode gekend zijn, aangetoond dat dit algoritme beter werkt dan bestaande algoritmes. Vervolgens worden experimenten uitgevoerd in een dynamische context, waarbij nieuwe orders arriveren terwijl de order picking operaties al aan de gang zijn. Uit deze experimenten blijkt dat het voordelig is om rekening te houden met eventuele toekomstige orders, door wat ruimte in de planning te behouden voor mogelijke nieuwe orders, om zo het serviceniveau op peil te houden in een dynamische context. Daarnaast wordt aangetoond dat wanneer orders eerder bekend worden, bijvoorbeeld doordat klanten iets eerder op de dag bestellen, de effici¨entie van de order picking activiteiten verhoogd kan worden. Vervolgens wordt dit algoritme op re¨ele data toegepast om de praktische relevantie van het algoritme aan te tonen. Deze studie op re¨ele data toont aan dat er een grote effici¨entiewinst te behalen valt door dit nieuwe algoritme te gebruiken in plaats van de huidige, eerder simplistische benadering door het bedrijf in kwestie. Deze effici¨entiewinsten staan toe om het geleverde serviceniveau te verbeteren en de kosten te verlagen. Op basis van deze re¨ele data wordt een wachtstrategie voorgesteld, waarbij orderpickers soms tijdelijk wachten met het beginnen aan een nieuwe picklijst wanneer er nog niet voldoende orders verzameld moeten worden. Door zo’n wachtstrategie te gebruiken, kan de effici¨entie van de order picking activiteiten verhoogd worden. Tot slot wordt het gecombineerde order picking and rittenplanningsprobleem in een business-to-consumer context bestudeerd. Ook hier geldt dat het ge¨ıntegreerd plannen van deze order picking en leveringsactiviteiten een effici¨entiewinst kan opleveren ten opzichte van het afzonderlijk inplannen van deze activiteiten. Vier metaheuristieken worden ontwikkeld om dit gecombineerde order picking en rittenplanningsprobleem aan te pakken, waarbij de verschillende metaheuristieken het probleem op een iets andere manier oplossen wat betreft de graad van integratie tussen de afzonderlijke problemen. Uit de experimenten blijkt dat de meer complexe algoritmes inderdaad beter in staat zijn om goede oplossingen voor het volledige orderbehandelingsproces te vinden. Daarnaast blijkt uit de experimenten ook hoe lastig het is voor bedrijven om aan veeleisende klanten, met korte levertermijnen in een beperkt tijdsvenster, tegemoet te komen. Kort samengevat blijkt uit deze thesis dat er, zowel voor de order picking activiteiten afzonderlijk als voor de activiteiten rond order picking en levering gecombineerd, grote effici¨entiewinsten te behalen zijn door de verschillende deelproblemen op een dynamische en ge¨ıntegreerde manier op te lossen in plaats van deze afzonderlijk in te plannen. Het anticiperen op toekomstige orders en het tijdelijk laten wachten van orderpickers voor ze aan een nieuwe taak beginnen wordt getest en blijkt een positief effect te hebben op de resultaten. De toepassing van het ontwikkelde algoritme op re¨ele data toont aan dat het voorgestelde algoritme tot sterk verbeterde resultaten leidt ten opzichte van de huidige werking van het magazijn. De kosten kunnen sterk gereduceerd worden zonder het serviceniveau in het gedrang te brengen. Tot slot wordt met de studie van het ge¨ıntegreerde order picking en rittenplanningsprobleem inzicht verworven in de uitdagingen van snelle leveringen binnen een e-commerce context. In een volgende stap kunnen deze inzichten gebruikt worden om meer effectieve prijszettingstrategie¨en voor de leveringskosten te ontwikkelen, aangezien leveringskosten die zijn afgestemd op de huidige operationele situatie kunnen bijdragen tot een effici¨entere orderbehandeling.