Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.

Thesis (MSc)--Stellenbosch University, 2003. / ENGLISH ABSTRACT: The South African government started the restructuring process of the state’s forest assets in 1998. The privatisation process includes all the assets of the South African Forestry Company (SAFCOL) and half of the former homelands’ 150 000 hectares of forest. In August 2000 SAFCOL released their “Operational Plan for Implementing Exit from Forestry in the Southem-Cape Portion of the Western Cape Region”. This plan identified only major land uses (agriculture, forestry, and conservation). A more detailed and intensive land evaluation study was required to specify land utilisation types that are tailor-made to each land unit of the study area. The main intention of this research study is to develop a more detailed evaluation process that elaborates on the land uses proposed by SAFCOL, which is site-specific in terms of the type of agricultural system to be used on specific areas, or the type of indigenous vegetation to be restored in conservation areas. La Motte plantation was taken as the case study and the SAFCOL digital database for the study area was used as the input data. The Automated Land Evaluation System (ALES) was the computer software package used to build the expert system to evaluate land according to the method presented in the FAO 1976 report. The ALES model built in this research study had 15 decision trees (one per land utilisation type) resulting in a total of 1678 branches, which relate land characteristics to severity levels of land qualities. During the computation of an evaluation ALES attempts to place each map unit into one of the four severity levels of land qualities within each landutilisation type. Physical suitability of each land unit for each land utilisation type was determined by the maximum limitation method. ALES is not a GIS and does not by itself display maps. The evaluation result matrix was exported into ArcMap for further optimisation and geographical analysis to enable the spatial representation of the results. After completion, taking into account the theoretical background, optimal terrain units were identified for the different land uses considered and the results are presented as tables and maps. Fynbos is the most suitable alternative land use for the study area followed by Pears, Sauvignon Blanc and Chardonnay vines. Pinotage, Shiraz, Cabernet Sauvignon and Cabernet Franc vines were least suitable as alternatives. The study found that the SAFCOL’s database is not sufficient to meet the requirements of a detailed site-specific land evaluation process. The polygon attribute table of the soil coverage only provided a subset of the land characteristics necessary to build and run the model. Data fields like soil form, depth, drainage, wetness, terrain type, aspect and climatic information had to be created because most of the data provided were in a non-digital form. The database was not complete and more precise data are needed to improve the system. / AFRIKAANSE OPSOMMING: Die Suid-Afrikaanse regering het in 1998 met die herstruktureringsproses van die bosboubates van die Staat begin. Die privatiseringsproses het al die bates van die Suid-Afrikaanse Bosboumaatskappy (SAFCOL) en die helfte van die vorige tuislande se 150 000 hektaar ingesluit. In Augustus 2000 het SAFCOL sy Operasionale Plan vrygestel vir die implementering van sy onttrekkingsprogram van bosbou uit die Suid-Kaap gedeelte van die Weskaap-streek. Hierdie plan het slegs die hoof landgebruike geidentifiseer, bv. landbou, bosbou en natuurbewaring. ‘n Meer gedetaileerde en intensiewe grondgebruikstudie was nodig om geskikte gebruikstipes te identifiseer wat optimale altematiewe gebruike spesifiseer vir elke landeenheid in die studie-area. Die hoofdoel van hierdie navorsingstudie is om ‘n meer gedetaileerde proses te ontwikkel ter uitbreiding van die altematiewe landgebruike wat deur SAFCOL voorgestel was. Hierdie voorstel moet meer ligging-spesifiek wees in terme van die tipe landbougewas of die tipe inheemse plantegroei wat in natuurbewaringsgebiede gevestig moet word. Die La Motte-plantasie is as voorbeeld gebruik om hierdie gevalle-studie te doen en die inligting is vanaf die SAFCOL digitale databasis verkry. Die rekenaar sagteware-pakket wat gebruik is om die land-evalueringstelsel te bou, is die “Automated Land Evaluation System” (ALES). Dit berus op die metode wat in die verslag van die FAO in 1976 voorgestel is. Die ALES model wat in hierdie navorsingstudie benut is, het 15 beslissingsbome (“decision-trees”) (een per landgebruikstipe) wat ‘n totaal van 1678 vertakkings lewer. Landeienskappe word hierdeur in verband gebring met verskillende geskiktheidsvlakke vir verskillende gewasse. Gedurende die berekening van hierdie evaluasie, het ALES elke gebiedseenheid in een van die vier geskiktheidsvlakke per grondgebruikstipe geplaas. Fisiese geskiktheid van elke landeenheid vir elke grondgebruikstipe is bepaal deur die maksimum beperkingsmetode. ALES is nie ‘n GIS nie en op sy eie vertoon dit nie kaarte nie. Die uitslag van die geskiktheidsmatriks is na ArcMap uitgevoer vir verdere optimisering en geografiese analises ten einde die resultate ruimtelik voor te stel. Na afhandeling, met inagneming van die teoretiese agtergrond, is optimale terrein-eenhede gei'dentifiseer met inagneming van die verskillende landgebruike en is die resultate in tabel en kaartvorm aangebied. Fynbos is die mees geskikte altematiewe landgebruik vir die studiegebied gevolg deur Pere, Sauvignon Blanc en Chardonnay wingerde. Pinotage, Shiraz, Cabernet Sauvignon en Cabernet Franc wingerde is minder geskikte altematiewe. Die studie het bevind dat die SAFCOL databasis nie voldoende was om aan die vereistes van ‘n gedetaileerde liggingspesifieke landevalueringsproses te voldoen nie. Die poligoon-attribuuttabel van die grondoorleg het net ‘n subversameling van die landeienskappe verskaf wat benodig was om die model te bou en uit te voer. Datavelde soos grondvorm, diepte, dreinering, vogtigheid, terreintipe, hellingrigting en klimaatinligting moes geskep word, omdat meeste van die data wat verskaf is nie in ‘n digitale vorm beskikbaar was nie. Die databasis was nie volledig nie en meer presiese data word benodig om die stelsel verder te verbeter.