Uncertainty in Crowd-Based Last-Mile Logistics

Internet est passé des e-mails dans les années 60 à la vente en ligne dans les années 90. Les premiers détaillants en ligne des années 90, comme Amazon, par exemple, détenaient une infime partie du marché par rapport aux détaillants géants de brique et de mortier, comme Walmart. Amazon a désormais dépassé Walmart en tant que plus grand détaillant au monde. La peur d'être infecté par des agents pathogènes dangereux, comme les coronavirus, dans les espaces publics a exacerbé le passage des achats physiques au commerce électronique. Faire les courses en toute sécurité chez soi et se faire livrer tous les articles a augmenté la demande pour la livraison à domicile. De plus, l'effet généralisé de la mondialisation, l'interconnectivité croissante des individus dans les sociétés et l'accessibilité croissante aux nouvelles technologies ont autonomisé les gens au début de ce siècle comme jamais auparavant, donnant naissance à une pléthore d'entreprises et d'organisations innovantes qui remettent en question le statu quo et contournent les barrières du marché qui protégeaient le pouvoir de méga-joueurs bien établis. Les petites startups surmontent les barrières du marché avec peu d'investissements ou d'infrastructures. Même le capital n'est plus un obstacle insurmontable pour les nouvelles entreprises comme il l'était auparavant, avec son accessibilité croissante via des canaux non conventionnels tels que le capital de risque, les investisseurs providentiels ou le financement participatif plus récent, où les personnes ordinaires avec un revenu moyen peuvent faire un petit ou grand apport de capital sur une communauté en ligne à quelqu'un qui travaille sur un projet qui lui plaît. Ces nouvelles entreprises sont non seulement en concurrence pour les marchés existants, mais elles en créent également de nouveaux, transforment les systèmes, modifient les comportements des clients et remettent en question les paradigmes commerciaux bien établis. En raison des nouvelles technologies et de la forte demande de livraisons à domicile, le «crowdshipping» est devenu une solution à faible coût pour satisfaire la demande. Le «crowdshipping» consiste à utiliser des véhicules personnels sous-utilisés, appartenant à des personnes ordinaires, pour effectuer les livraisons. Les chauffeurs indépendants sont des personnes qui possèdent un véhicule et sont prêtes à livrer des colis moyennant une indemnisation. Contrairement aux chauffeurs professionnels, les chauffeurs indépendants sont libres de choisir quand et comment ils travaillent. Les chauffeurs indépendants ont un ensemble de caractéristiques inconnues qui représentent un défi lors de la planification des itinéraires de livraison. Ils pourraient avoir un déplacement prévu avec une destination fixe et pourraient être disposés à livrer certains colis tant que la distance totale ajoutée à leur déplacement prévu n'est pas trop longue. Globalement, la volonté de livrer des colis peut être conditionnée par une série de préférences personnelles, par exemple, le montant de la compensation ou les conditions météorologiques. De plus, les véhicules des chauffeurs indépendants ne sont pas conçus pour la livraison de colis. Les chauffeurs indépendants ont des véhicules de différents modèles, certains peuvent être de petits véhicules, d'autres peuvent être de grande taille. L'offre de chauffeurs indépendants dépendrait de ces préférences. Traditionnellement, les problèmes de tournées de véhicules stochastiques tiennent compte de l'incertitude qui provient des clients, par exemple, des demandes stochastiques. Dans le «crowdshipping», l'incertitude peut provenir des chauffeurs indépendants, ce qui représente un changement de paradigme. L'objectif de cette thèse est d'identifier et d'explorer les principales sources d'incertitude dans la logistique du dernier kilomètre basée sur le recours à des chauffeurs indépendants et de développer des outils mathématiques pour obtenir des informations précieuses sur ces propriétés stochastiques. Le chapitre 4 introduit une nouvelle variante stochastique du problème de tournées de véhicules. Une plateforme de «crowdshipping» doit satisfaire un ensemble de demandes de livraison d'un dépôt central avec une flotte mixte des véhicules professionnels et des chauffeurs indépendants. L'offre de chauffeurs indépendants est considérée comme stochastique, ainsi, les itinéraires créés pour les chauffeurs indépendants pourraient potentiellement être rejetés, entraînant des coûts supplémentaires. Des actions de recours sont introduites qui considèrent l'utilisation de véhicules réguliers pour desservir les itinéraires rejetés par les chauffeurs indépendants. Une formulation de programmation stochastique en deux étapes est proposée et un algorithme exact de «branch-and-price» est développé pour résoudre de grandes instances avec 100 clients. Un algorithme d'évaluation cohérent est développé pour résoudre tous les problèmes d'évaluation d'itinéraires en un seul. Les limites supérieures sont dérivées du nombre total d'itinéraires qui devraient être offerts aux chauffeurs indépendants potentiels. La probabilité de rejet d'itinéraire est modélisée comme dépendant de l'ensemble d'itinéraires proposés aux chauffeurs indépendants. La valeur de la solution stochastique s'élève à 21%. Une analyse de sensibilité est effectuée sur les hypothèses d'acceptation des itinéraire. Cette analyse montre qu'il n'y a aucune différence entre donner la priorité à l'attribution des itinéraires les plus coûteux aux chauffeurs indépendants en premier et l'hypothèse selon laquelle les chauffeurs indépendants choisiront en premier l'itinéraire le mieux compensé. Le Chapitre 5 introduit une nouvelle variante stochastique du problème de tournées de véhicules où la destination des chauffeurs indépendants peut être stochastique. Les chauffeurs indépendants ne souhaitent pas s'écarter beaucoup de leurs destinations. Les destinations peuvent changer d'un jour à l'autre en fonction des préférences des chauffeurs indépendants. Une contrainte de durée de parcours est prise en compte sous l'hypothèse que cela peut augmenter la participation. Un modèle stochastique en deux étapes est proposé et une heuristique de génération de colonnes est développée pour résoudre les grandes instances. Les résultats montrent que la localisation géographique des destinations peut avoir un impact sur le coût total espéré. Les destinations plus éloignées du dépôt réduisent le plus le coût prévu de l'opération. Une analyse de sensibilité sur la structure de coûts montre que les instances dont les destinations sont éloignées du dépôt central sont plus sensibles au coût variable qu'au coût fixe. Lorsque la rémunération variable est suffisamment élevée, les instances avec des destinations de chauffeurs indépendants à proximité immédiate du dépôt central réduisent le plus le coût espéré. Enfin, le Chapitre 6 considère le cadre du chapitre 4 et détermine la valeur de compensation à payer aux chauffeurs indépendants. Lorsque la rémunération est trop élevée, les chauffeurs indépendants ne sont pas une bonne option par rapport à la flotte de véhicules professionnels. Lorsque la compensation est trop faible, les chauffeurs indépendants ne veulent pas participer. Un équilibre de marché est trouvé qui minimise le coût total espéré des opérations compte tenu l'incertitude sur le niveau de participation des chauffeurs indépendants.

Abstract

The internet went from e-mails in the 60s to online retailing in the 90s. Early online retailers in the 90s, e.g., Amazon, had a minuscule portion of the market when compared to giant brick-and-mortar retailers, e.g., Walmart. Amazon has now surpassed Walmart as the world's biggest retailer. The fear of being infected by egregious pathogens, e.g., corona viruses, in public areas has exacerbated the shift from brick-and-mortar shopping to e-commerce. Shopping from the safety of your own home and having all the items delivered, has increased demand for home delivery. Moreover, the widespread effect of globalization, the increasing inter-connectivity of individuals in societies, and the rising accessibility to new technologies, have empowered people at the beginning of this century like never before, giving rise to a plethora of innovative companies and organizations that are challenging the status quo and circumventing market barriers that protected the power of well-established mega-players. Small startups are overcoming market barriers with little investment or infrastructure. Even capital is no longer an insurmountable barrier for new companies as it used to be, with its increasing accessibility through unconventional channels such as venture capitalism, angel investors, or the more recent, crowd-funding, where regular people with an average income can make a small or large contribution of capital on an online community to someone who is working on a project that is of their liking. These new companies are not only competing for existing markets, but are also creating new ones, transforming systems, changing customer behaviors and challenging well-established business paradigms. As a consequence of the new technologies and the high demand for home deliveries, crowdshipping has emerged as a low-cost solution to satisfy the demand. Crowd-shipping consists of using under-utilized personal vehicles, owned by regular people, to fulfill deliveries. Crowddrivers are individuals who own a vehicle and are willing to deliver packages for a compensation. In contrast to professional drivers, crowd-drivers are free to choose when and how they work. Crowd-drivers have a set of unknown characteristics that represents a challenge when planning delivery routes. They could have a planned trip with a fixed destination, and could be willing to deliver some packages as long as the total distance added to their planned trip is not too long. Overall, the willingness to deliver packages can be conditioned on a series of personal preferences, e.g., the amount of the compensation or weather conditions. In addition, crowd-driver vehicles are not designed for parcel delivery. Crowd-drivers have vehicles of various models; some can be small vehicles, others can be large. The supply of crowd-drivers would depend on such preferences. Traditionally, stochastic vehicle routing problems consider the uncertainty that originates from customers, e.g, stochastic demands. In crowd-shipping, uncertainty can originate from crowd-drivers, this represents a paradigm shift. The objective of this dissertation is to identify and explore the main sources of uncertainty in crowd-based last-mile logistics and to develop mathematical tools to gain valuable insights about these stochastic properties. Chapter 4 introduces a new stochastic variant of the vehicle routing problem. A crowd-shipping platform must satisfy a set of delivery requests from a central depot with a mixed fleet of professional vehicles and crowd-drivers. The supply of crowd-drivers is considered to be stochastic, thus, routes created for crowd-drivers could potentially be rejected, causing additional costs. Recourse actions are introduced that consider the use of regular vehicles to fulfill routes rejected by crowd-drivers. A two-stage stochastic programming formulation is proposed and an exact branch-and-price algorithm is developed to solve large instances with 100 customers. A cohesive pricing algorithm is developed to solve all pricing problems in a single one. Upper bounds are derived for the total number of crowd-driver routes that should be offered to potential crowd-drivers. The probability of route rejection is modeled as dependent on the complete set of routes that are offered to crowd-drivers. The value of the stochastic solution is shown to be as high as 21%. A sensitivity analysis is performed on the assumptions of route acceptance, which shows no difference between prioritizing the assignment of the most costly routes to crowd-drivers first or the assumption that crowddrivers will choose the best compensated route first. Chapter 5 introduces a new stochastic variant of the vehicle routing problem where the destination of crowd-drivers can be stochastic. Crowd-drivers do not wish to deviate much from their destinations. Destinations can change from day to day based on crowd-drivers' preferences. A route duration constraint is considered to increase participation. A twostage stochastic model is proposed and a column generation heuristic is developed to solve large instances. The results show that the geographic location of destinations can have an impact in the total expected cost. Destinations that are further from the depot reduce the expected cost of the operation the most. A sensitivity analysis on the cost structure shows that instances with destinations far from the central depot are more sensitive to the variable cost than to the fixed cost. When the variable compensation is sufficiently high, the instances with crowd-driver destinations in close proximity to the central depot reduce the expected cost the most. Finally, Chapter 6 considers the setting of Chapter 4 and determines the compensation value to be paid to crowd-drivers. When the compensation is too high, crowd-drivers are not a good option compared to the professional fleet of vehicles. When the compensation is too low crowd-drivers do not want to participate. A market equilibrium is found that minimizes the total expected cost of operations under uncertainty of crowd-driver participation.