Um die anderen Arten von Veröffentlichungen zu diesem Thema anzuzeigen, folgen Sie diesem Link: Workforce Scheduling and Routing Problem.
Dissertationen zum Thema „Workforce Scheduling and Routing Problem“
Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an
Machen Sie sich mit Top-50 Dissertationen für die Forschung zum Thema "Workforce Scheduling and Routing Problem" bekannt.
Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.
Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.
Sehen Sie die Dissertationen für verschiedene Spezialgebieten durch und erstellen Sie Ihre Bibliographie auf korrekte Weise.
1
Algethami, Haneen. „Genetic algorithms for workforce scheduling and routing problem“. Thesis, University of Nottingham, 2017. http://eprints.nottingham.ac.uk/47712/.
Der volle Inhalt der QuelleAnnotation:
The Workforce Scheduling and Routing Problem (WSRP) is described as the assignment of personnel to visits across various geographical locations. Solving this problem demands tackling scheduling and routing constraints while aiming to minimise the total operational cost. With current computational capabilities, small WSRPs are solvable using exact methods. However, it is difficult to solve when they are larger. The difficulty of WSRP is further increased when processing conflicting assignments or dealing with workers unavailability at customer's areas. Genetic Algorithms (GAs) have proved their effectiveness in these regards, because of their search capability to acquire good solutions in a reasonable computational time. A GA consists of many components, which can be chosen and combined in numerous procedures. In the case of solving scheduling and routing problems separately, different GAs have been proposed. When solving WSRP problem instances, it has been quite common to use the design components, intended for scheduling or routing problems. In this thesis, 42 real-world Home Health Care (HHC) planning problem datasets are used as instances of the WSRP. Different GA components are presented in this study, tailored for the combined settings. This has made major contributions to understanding how GAs works in a challenging real-world problem. Research interests in this work are categorised into two parts. The first part aims to understand how to employ different genetic operators effectively when solving WSRPs. The work intends to design and select the best combination of components that provide good solutions. Accordingly, seven well-known crossovers, three mutation operators and eight cost-based operators are implemented. In addition, two repair heuristics to tackle infeasibility. Nevertheless, a direct chromosome representation has resulted in poor solutions. Thus, there is a need for more tailored components for this problem. Therefore, an indirect chromosome representation, designed specifically to tackle WSRPs, is presented. The aim is to ensure initial solutions feasibility. Due to the quality of solutions, the GA introduced is considered an effective baseline evolutionary algorithm for WSRP. This work also suggested that each problem set requires different parameter settings. The second research interest intends to increase the GA efficiency. One approach is to investigate the effect of using adaptive components on the quality of WSRPs solutions. The aim is to adaptively alter parameter values instead of tuning an algorithm to a specific instance. Three aspects are adjusted during the run according to different rules: operator rates, population size, and crossover operator function. Thus, six variations of a diversity-based adaptive GA is presented. Not only the adaptive GA has improved the results, especially for large WSRP scenarios, but also it reduces the computational time. Another aspect investigated is the effect of using a group of crossover operators rather than using one operator throughout the search. Six crossover operators, well known and problem-specific are used as part of a multiple crossover GA framework. To evaluate an operator effectiveness, a reinforcement-learning model is developed with three performance measurements. The most successful variant of this algorithm finds the best-known results for the larger problem instances and matching the best-known results for some of the smaller ones. When combining this method with the adaptive GA, it provided some of the best results, as compared to established algorithms. The presented methods have contributed in reducing the operational costs for this constrained combinatorial optimisation problem.
2
Laesanklang, Wasakorn. „Heuristic decomposition and mathematical programming for workforce scheduling and routing problems“. Thesis, University of Nottingham, 2017. http://eprints.nottingham.ac.uk/39883/.
Der volle Inhalt der QuelleAnnotation:
This thesis presents a PhD research project using a mathematical programming approach to solve a home healthcare problem (HHC) as well as general workforce scheduling and routing problems (WSRPs). In general, the workforce scheduling and routing problem consists of producing a schedule for mobile workers to make visits at different locations in order to perform some tasks. In some cases, visits may have time-wise dependencies in which a visit must be made within a time period depending on the other visit. A home healthcare problem is a variant of workforce scheduling and routing problems, which consists in producing a daily schedule for nurses or care workers to visit patients at their home. The scheduler must select qualified workers to make visits and route them throughout the time horizon. We implement a mixed integer programming model to solve the HHC. The model is an adaptation of the WSRP from the literature. However, the MIP solver cannot solve a large-scale real-world problem defined in this model form because the problem requires large amounts of memory and computational time. To tackle the problem, we propose heuristic decomposition approaches which split a main problem into sub-problems heuristically and each sub-problem is solved to optimality by the MIP solver. The first decomposition approach is a geographical decomposition with conflict avoidance (GDCA). The algorithm avoids conflicting assignments by solving sub-problems in a sequence in which worker's availabilities are updated after a sub-problem is solved. The approach can find a feasible solution for every HHC problem instance tackled in this thesis. The second approach is a decomposition with conflict repair and we propose two variants: geographical decomposition with conflict repair (GDCR) and repeated decomposition and conflict repair (RDCR). The GDCR works in the same way as GDCA but instead of solving sub-problems in a given sequence, they are solved with no specific order and conflicting assignments are allowed. Later on, the conflicting assignments are resolved by a conflicting assignments repair process. The remaining unassigned visits are allocated by a heuristic assignment algorithm. The second variant, RDCR, tackles the unassigned visits by repeating the decomposition and conflict repair until no further improvement has been found. We also conduct an experiment to use different decomposition rules for RDCR. Based on computational experiments conducted in this thesis, the RDCR is found to be the best of the heuristic decomposition approaches. Therefore, the RDCR is extended to solve a WSRP with time-dependent activities constraints. The approach requires modification to accommodate the time-dependent activities constraints which means that two visits may have time-wise requirements such as synchronisation, time overlapped, etc. In addition, we propose a reformulated MIP model to solve the HHC problem. The new model is considered to be a compact model because it has significantly fewer constraints. The aim of the reformulation is to reduce the solver requirements for memory and computational time. The MIP solver can solve all the HHC instances formulated in a compact model. Most of solutions obtained with this approach are the best known solutions so far except for those the instances for which the optimal solution can be found using the full MIP model. Typically, this approach requires computational time below one hour per instance. This problem reformulation is so far the best approach to solve the HHC instances considered in this thesis. The heuristic decomposition and model reformulation proposed in this thesis can find solutions to the real-world home healthcare problem. The main achievement is the reduction of computational memory and computational time which are required by the optimisation solver. Our studies show the best way to control the use of solver memory is the heuristic decomposition approach, particularly the RDCR method. The RDCR method can find a solution for every instance used throughout this thesis and keep the memory usage within personal computer memory ranges. Also, the computational time required to solve an instance being less than 8 minutes, for which the solution gap to the optimal solution is on average 12%. In contrast, the strong point of the model reformulation approach over the heuristic decomposition is that the model reformulation provides higher quality solutions. The relative gaps of solutions between the solution for solving the reformulated model and the solution from solving the full model is less than 1% whilst its the computational time could be up to one hour and its computational memory could require up to 100 GB. Therefore, the heuristic decomposition approach is a method for finding a solution using restricted resources while the model reformulation is an approach for when a high solution quality is required. Hence, two mathematical programming based heuristic approaches are each more suitable in different circumstances in which both find high quality solutions within an acceptable time limit.
3
Lerouge, Mathieu. „Designing and generating user-centered explanations about solutions of a Workforce Scheduling and Routing Problem“. Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPAST174.
Der volle Inhalt der QuelleAnnotation:
Les systèmes d'aide à la décision basés sur l'optimisation combinatoire trouvent des applications dans divers domaines professionnels. Cependant, les décideurs qui utilisent ces systèmes ne comprennent souvent pas les concepts mathématiques et les principes algorithmiques qui les sous-tendent. Ce manque de compréhension peut entraîner du scepticisme et une réticence à accepter les solutions générées par le système, érodant ainsi la confiance placée dans le système. Cette thèse traite cette problématique dans le cas du problème de planification d'employés mobiles, en anglais Workforce Scheduling and Routing Problem (WSRP), un problème d'optimisation combinatoire couplant de l'allocation de ressources humaines et du routage.Tout d'abord, nous proposons un cadre qui modélise le processus d'explication de solutions pour les utilisateurs d'un système de résolution de WSRP, permettant d'aborder une large gamme de sujets. Les utilisateurs initient le processus en faisant des observations sur une solution et en formulant des questions liées à ces observations grâce à des modèles de texte prédéfinis. Ces questions peuvent être de type contrastif, scénario ou contrefactuel. D'un point de vue mathématique, elles reviennent essentiellement à se demander s'il existe une solution faisable et meilleure dans un voisinage de la solution courante. Selon les types de questions, cela conduit à la formulation d'un ou de plusieurs problèmes de décision et de programmes mathématiques.Ensuite, nous développons une méthode pour générer des textes d'explication de différents types, avec un vocabulaire de haut niveau adapté aux utilisateurs. Notre méthode repose sur des algorithmes efficaces calculant du contenu explicatif afin de remplir des modèles de textes d'explication. Des expériences numériques montrent que ces algorithmes ont des temps d'exécution globalement compatibles avec une utilisation en temps quasi-réel des explications par les utilisateurs.Enfin, nous présentons un design de système structurant les interactions entre nos techniques de génération d'explications et les utilisateurs qui reçoivent les textes d'explication. Ce système sert de base à un prototype d'interface graphique visant à démontrer l'applicabilité pratique et les potentiels bénéfices de notre approche dans son ensembleDecision support systems based on combinatorial optimization find application in various professional domains. However, decision-makers who use these systems often lack understanding of their underlying mathematical concepts and algorithmic principles. This knowledge gap can lead to skepticism and reluctance in accepting system-generated solutions, thereby eroding trust in the system. This thesis addresses this issue in the case of the Workforce Scheduling and Routing Problems (WSRP), a combinatorial optimization problem involving human resource allocation and routing decisions.First, we propose a framework that models the process for explaining solutions to the end-users of a WSRP-solving system while allowing to address a wide range of topics. End-users initiate the process by making observations about a solution and formulating questions related to these observations using predefined template texts. These questions may be of contrastive, scenario or counterfactual type. From a mathematical point of view, they basically amount to asking whether there exists a feasible and better solution in a given neighborhood of the current solution. Depending on the question types, this leads to the formulation of one or several decision problems and mathematical programs.Then, we develop a method for generating explanation texts of different types, with a high-level vocabulary adapted to the end-users. Our method relies on efficient algorithms for computing and extracting the relevant explanatory information and populates explanation template texts. Numerical experiments show that these algorithms have execution times that are mostly compatible with near-real-time use of explanations by end-users. Finally, we introduce a system design for structuring the interactions between our explanation-generation techniques and the end-users who receive the explanation texts. This system serves as a basis for a graphical-user-interface prototype which aims at demonstrating the practical applicability and potential benefits of our approach
4
Xie, Fulin. „Models and algorithms for workforce scheduling and routing problems in emergency response services“. Thesis, University of Southampton, 2018. https://eprints.soton.ac.uk/422176/.
Der volle Inhalt der QuelleAnnotation:
Emergency response services play a key role in protecting public safety and health, and therefore developing effective and efficient response systems is of critical importance. In this thesis, we focus on the workforce scheduling and routing problems (WSRPs) that are commonly faced by emergency response organisations. We first present a simulation model for real-time emergency vehicle dispatching and routing, developed based on a case study of a British company providing emergency road services. The developed model is used to evaluate system performance, test scenarios and compare the effectiveness of different dispatching policies. The results of simulation study motivate us to design more advanced heuristic algorithms for the static WSRP. To this purpose, we develop a simple and fast algorithm based on the iterated local search (ILS) framework. The performance of the proposed algorithm is evaluated on benchmark instances against an off-the-shelf optimizer and an existing adaptive large neighbourhood search algorithm. The proposed ILS algorithm is also applied to solve the skill vehicle routing problem, which can be viewed as a special case of the WSRP. To further improve the decision making, we exploit the stochastic information about future requests and integrate this part of information into the solution method for the dynamic WSRP. A stochastic set-partitioning model is described and integrated with a sampling-based approach. The proposed model uses a two-stage framework, where the first-stage is concerned with finding a set of feasible routes covering known requests, while the second-stage estimates the effect of the same routes with respect to future requests. The performance of the proposed model is evaluated against a deterministic model and a naive greedy heuristic within a simulation framework.
5
Fransson, Rasmus, und Michael Janfjord. „Online Workforce Scheduling and Routing : A case study at an on-site service provider“. Thesis, Luleå tekniska universitet, Institutionen för ekonomi, teknik och samhälle, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-64125.
Der volle Inhalt der QuelleAnnotation:
The consumer market of today is characterized by emphasis on superior customer satisfaction and personalization of services. This entails higher customer expectations on organizations, which also includes the workforce scheduling processes in which the consumers expect more decision-power to dictate what they want, when and where they want services to be delivered. For organizations that deliver on-site services, the routing aspect becomes an important part of the scheduling process. Literature on Workforce Scheduling and Routing Problems (WSRP) seldom relate to characteristics of the more dynamic consumer market. As the markets and consumer needs become more flexible, the relevance for research concerning these characteristics increases. This study addresses this by reviewing current literature and present common solution methodologies applied to WSRP, as well as the effects of the online scheduling characteristics. With this as a foundation, a discussion is provided of how WSRP and online scheduling can be combined in order to improve resource utilization and minimize travel time for an on-site service provider. The overall aim of the study is to investigate how an online WSRP with exact time windows can be formulated and solved. The result is a four-stage hybrid method including linear integer programming and constructive heuristics with the objective to minimize travel time, idle time, and the makespan in the schedules. A case study has been conducted on an on-site service provider, and by applying the proposed hybrid methodology on the case company’s scheduling process, results have been obtained that demonstrates improvements of travel time and resource utilization. The study also demonstrate that the appliance of flexible travel times and product dependent service times have positive impact on the quality of the generated schedules. A key insight is that organizations working with exact time windows have to be aware of the trade-off between customer preferences and operational efficiency in day-to-day operations. Thus, organizations have to decide what holds most importance to the organization’s long-term success.
6
Castillo, Salazar José Arturo. „Optimisation models and algorithms for workforce scheduling and routing“. Thesis, University of Nottingham, 2015. http://eprints.nottingham.ac.uk/30886/.
Der volle Inhalt der QuelleAnnotation:
This thesis investigates the problem of scheduling and routing employees that are required to perform activities at clients’ locations. Clients request the activities to be performed during a time period. Employees are required to have the skills and qualifications necessary to perform their designated activities. The working time of employees must be respected. Activities could require more than one employee. Additionally, an activity might have time-dependent constraints with other activities. Time-dependent activities constraints include: synchronisation, when two activities need to start at the same time; overlap, if at any time two activities are being performed simultaneously; and with a time difference between the start of the two activities. Such time difference can be given as a minimum time difference, maximum time difference, or a combination of both (min-max). The applicability of such workforce scheduling and routing problem (WSRP) is found in many industries e.g. home health care provision, midwives visiting future mothers, technicians performing installations and repairs, estate agents showing residences for sale, security guards patrolling different locations, etc. Such diversity makes the WSRP an important combinatorial optimisation problem to study. Five data sets, obtained from the literature, were normalised and used to investigate the problem. A total of 375 instances were derived from these data sets. Two mathematical models, an integer and a mixed integer, are used. The integer model does not consider the case when the number of employees is not enough to perform all activities. The mixed integer model can leave activities unassigned. A mathematical solver is used to obtain feasible solutions for the instances. The solver provides optimal solutions for small instances, but it cannot provide feasible solutions for medium and large instances. This thesis presents the gradual development of a greedy heuristic that is designed to tackle medium and large instances. Five versions of the greedy heuristic are presented, each of them obtains better results than the previous one. All versions are compared to the results obtained by the mathematical solver when using the mixed integer model. The greedy heuristic exploits domain information to speed the search and discard infeasible solutions. It uses tailored functions to deal with each of the time-dependent activity constraints. These constraints make more difficult the solution process. Further improvements are obtained by using tabu search. It provides moves based on the tailored functions of the greedy heuristic. Overall, the greedy heuristic and the tabu search, maintain feasible solutions at all times. The main contributions of this thesis are: the definition of WSRP; the introduction of 375 instances based on five data sets; the adaptation of two mathematical models; the introduction of a greedy heuristic capable of obtaining better results than the solver; and, the implementation of a tabu search to further improve the results.
7
Al-Hamad, Khaled. „Tabu search for ship routing and scheduling“. Thesis, Brunel University, 2006. http://bura.brunel.ac.uk/handle/2438/5071.
Der volle Inhalt der QuelleAnnotation:
This thesis examines exact and heuristic approaches to solve the Ship Routing and Scheduling Problem (SRSP). The method was developed to address the problem of loading cargos for many customers using heterogeneous vessels. Constraints relate to delivery time windows imposed by customers, the time horizon by which all deliveries must be made and vessel capacities. The objective is to minimise the overall operation cost, where all customers are satisfied. Two types of routing and scheduling are considered, one called single-cargo problem, where only one cargo can be loaded into a ship, and the second type called multi-cargo problem, where multiple products can be carried on a ship to be delivered to different customers. The exact approach comprises two stages. In the first stage, a number of candidate feasible schedules is generated for each ship in the fleet. The second stage is to model the problem as a set partitioning problem (SPP) where the columns are the candidate feasible schedules obtained in the first stage. The heuristic approach uses Tabu Search (TS). Most of the TS operations, such as insert and swap moves, tenure, tabu list, intensification, and diversification are used. The results of a computational investigation are presented. Solution quality and execution time are explored with respect to problem size and parameters controlling the tabu search such as tenure and neighbourhood size. The results showed that the average of the solution gap between TS solution and SPP solution is up to 28% (for small problems) and up to 18% for large problems. However, obtaining an optimal solution requires a large amount of computer time to produce the solution compared to obtaining approximate solutions using the TS approach. The use of Tabu Search for SRSP is novel and the results indicate that it is viable approach for large problems.
8
Bögl, Michael, Karl Doerner und Sophie N. Parragh. „The School Bus Routing and Scheduling Problem with Transfers“. Wiley Periodicals, Inc, 2015. http://dx.doi.org/10.1002/net.21589.
Der volle Inhalt der QuelleAnnotation:
In this article, we study the school bus routing and scheduling problem with transfers arising in the field of nonperiodic public transportation systems. It deals with the transportation of pupils from home to their school in the morning taking the possibility that pupils may change buses into account. Allowing transfers has several consequences. On the one hand, it allows more flexibility in the bus network structure and can, therefore, help to reduce operating costs. On the other hand, transfers have an impact on the service level: the perceived service quality is lower due to the existence of transfers; however, at the same time, user ride times may be reduced and, thus, transfers may also have a positive impact on service quality. The main objective is the minimization of the total operating costs. We develop a heuristic solution framework to solve this problem and compare it with two solution concepts that do not consider transfers. The impact of transfers on the service level in terms of time loss (or user ride time) and the number of transfers is analyzed. Our results show that allowing transfers reduces total operating costs significantly while average and maximum user ride times are comparable to solutions without transfers. (authors' abstract)
9
Cowling, Peter I., N. J. Colledge, Keshav P. Dahal und Stephen M. Remde. „The trade off between diversity and quality for multi-objective workforce scheduling“. Springer-Verlag, 2006. http://hdl.handle.net/10454/2511.
Der volle Inhalt der QuelleAnnotation:
In this paper we investigate and compare multi-objective and
weighted single objective approaches to a real world workforce scheduling
problem. For this difficult problem we consider the trade off in solution quality
versus population diversity, for different sets of fixed objective weights. Our
real-world workforce scheduling problem consists of assigning resources with
the appropriate skills to geographically dispersed task locations while satisfying
time window constraints. The problem is NP-Hard and contains the Resource
Constrained Project Scheduling Problem (RCPSP) as a sub problem. We investigate
a genetic algorithm and serial schedule generation scheme together with
various multi-objective approaches. We show that multi-objective genetic algorithms
can create solutions whose fitness is within 2% of genetic algorithms using
weighted sum objectives even though the multi-objective approaches know
nothing of the weights. The result is highly significant for complex real-world
problems where objective weights are seldom known in advance since it suggests
that a multi-objective approach can generate a solution close to the user
preferred one without having knowledge of user preferences.
10
Yuan, Lufeng. „A Heuristic Approach for the Home Health Care Scheduling and Routing Problem“. Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/41277.
Der volle Inhalt der QuelleAnnotation:
Abstract
Home Health Care (HHC) is a health care service delivered by sending caregivers such as nurses or personal support workers (PSW) to visit patients in their homes. The assignment of patients to nurses as well as the sequencing of patients for each nurse is called the Home Health Care Scheduling and Routing Problem (HHCSRP). This thesis proposes a heuristic approach to solve HHCSRP to which it is hard and even impossible to obtain an optimal solution for relative larger instances in a reasonable amount of computational time by using an exact algorithm as HHCSRP is NP hard. In the approach, this thesis developed and contributed a heuristic partition method to partition patients into a number of single nurse groups. The computational test result shows that the proposed approach can achieve good solutions which remain within 5% of the commercial solver CPLEX’s best solution using an acceptable solution time on all test instances.
11
Bowden, Zachary E. „Behavioral Logistics and Fatigue Management in Vehicle Routing and Scheduling Problems“. Diss., Virginia Tech, 2016. http://hdl.handle.net/10919/79792.
Der volle Inhalt der QuelleAnnotation:
The vehicle routing problem (VRP), is a classic optimization problem that aims to determine the optimal set of routes for a fleet of vehicles to meet the demands of a set of customers. The VRP has been studied for many decades and as such, there are many variants and extensions to the original problem. The research presented here focuses on two different types of vehicle routing and scheduling planning problems: car shipping and fatigue-aware scheduling. In addition to modeling and solving the car shipping problem, this research presents a novel way for ways in which drivers can describe their route preferences in a decision support system. This work also introduces the first fatigue-aware vehicle scheduling problem called the Truck Driver Scheduling Problem with Fatigue Management (TDSPFM). The TDSPFM is utilized to produce schedules that keep the drivers more alert than existing commercial vehicle regulations. Finally, this work analyzes the effect of the starting alertness level on driver alertness for the remainder of the work week and examines a critical shortcoming in existing regulations.Ph. D.
12
Brandao, Jose Carlos Soares. „A decision support system and algorithms for the vehicle routing and scheduling problem“. Thesis, Lancaster University, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.238909.
Der volle Inhalt der Quelle
13
Seixas, Michel Povlovitsch. „Heuristic and exact methods applied to a rich vehicle routing and scheduling problem“. Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/3/3135/tde-09072014-111258/.
Der volle Inhalt der QuelleAnnotation:
This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree.Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.
14
De, Castro Pena Guilherme. „Models and Methods for the Integrated Scheduling Routing Problem Applied to Major Disasters“. Thesis, Troyes, 2021. http://www.theses.fr/2021TROY0033.
Der volle Inhalt der QuelleAnnotation:
Le nettoyage des débris dans les zones urbaines après des catastrophes majeures est très important pour permettre aux habitants de se remettre de leurs effets. Lors de catastrophes, une zone inattendue et étendue peut être touchée. De plus, le temps et les coûts pour effectuer les opérations de nettoyage peuvent être très élevés. Cette thèse aborde le problème intégré multi-période de planification et de tournées de véhicules pour nettoyer les débris (SRP-CD) après des catastrophes majeures. Le problème comprend des décisions stratégiques (planification) et opérationnelles (tournées) et prend en compte des questions complexes telles que deux niveaux de synchronisation : entre les équipes de travail et les camions-bennes, et entre les camions-bennes nécessaires pour charger, transporter et décharger les débris pendant les journées de travail. L'objectif du SRP-CD est double : minimiser le nombre de jours pour le nettoyage global, au niveau stratégique, et minimiser le coût total de routage des véhicules, au niveau opérationnel. Un nouveau modèle mathématique basé sur une formulation dynamique multi-flot, des heuristiques constructives, des métaheuristiques basées sur la recherche par grand voisinage (LNS) et des métaheuristiques hybrides basées sur la LNS et le recuit simulé sont proposés. Des expérimentations pour le modèle et les approches sont réalisées, afin de mesurer la performance et la robustesse des méthodes proposées. A notre connaissance, ce sont les premières contributions dans la littérature pour le SRP-CD, incluant tous les aspects abordés dans cette thèseCleaning debris in urban areas after major disasters is very relevant to inhabitants to recover from their effects. In natural disasters, an unexpected and large area can be affected. Moreover, the time and the costs to perform the cleaning operations can be very high. In this work, the integrated multi-period scheduling routing problem to clean debris (SRP-CD) after major disasters is investigated. The problem includes strategical (scheduling) and operational (routing) decisions, considering complex issues such as two levels of synchronization between work-troops and dump trucks, and between dump trucks necessary to load, transport and unload debris during limited working days. The goal of SRP-CD is twofold: minimizing the number of days for the overall cleaning, in the strategical level; and minimizing the total costs of vehicle routes in the operational level. A new mathematical model based on a dynamic multi-flow formulation, constructive heuristics, Large Neighborhood Search (LNS)-based metaheuristics and hybrid metaheuristics based on LNS and Simulated Annealing are proposed. Comparison experiments for the model and the approaches are carried out to measure performance and robustness of the proposed methods. To the best of our knowledge, these are the first contributions in the literature for SRP-CD, including all the aspects addressed in this thesis
15
Shi, Yong. „Modeling and Solving Home Health Care Routing and Scheduling Problem with Consideration of Uncertainties“. Thesis, Bourgogne Franche-Comté, 2018. http://www.theses.fr/2018UBFCA027.
Der volle Inhalt der QuelleAnnotation:
Les soins de santé à domicile (HHC) sont un large éventail de services de santé pouvant être dispensés à domicile pour une maladie ou une blessure. Ces dernières années, le secteur des soins de santé est devenu l'un des plus grands secteurs de l'économie des pays développés. L'un des défis les plus importants dans le domaine des HHC consiste à affecter plus efficacement les ressources en main-d'œuvre et les équipements sous des ressources limitées. Étant donné que le coût du transport est l’une des dépenses les plus critiques dans les activités de l’entreprise, il est très important d’optimiser le problème de routage des véhicules pour les sociétés HHC.Cependant, la majorité des travaux existants ne prennent en compte que le modèle déterministe. Dans la pratique de HHC, le décideur et les aidants rencontrent souvent des incertitudes. Il est donc essentiel d'intégrer l'incertitude dans le modèle pour établir un calendrier raisonnable pour la société HHC. Cette thèse aborde le problème du routage et de la planification HHC en prenant en compte respectivement la demande non déterministe, le service et le temps de parcours. Le corps principal de la thèse est composé de trois œuvres indépendantes.(1) Sur la base de la théorie de la crédibilité floue, nous avons proposé un modèle de programmation par contraintes de hasard flou (FCCP) pour le problème de routage HHC avec une demande floue. Ce modèle présente à la fois des caractéristiques d'optimisation combinatoire et de FCCP. Pour faire face au problème à grande échelle, nous avons développé un algorithme génétique hybride avec la simulation de Monte Carlo. Trois séries d'expériences ont été menées pour valider les performances du modèle et de l'algorithme proposés. Enfin, l’analyse de sensibilité a également porté sur l’observation du paramètre variable impliqué dans la prise de décision floue.(2) En fonction de l'activité des soignants de HHC, nous avons proposé un modèle de programmation stochastique en deux étapes avec recours (SPR) pour la livraison et la reprise simultanées avec des temps de trajet et de service stochastiques dans HHC. Pour résoudre le modèle, nous avons d’une part réduit le modèle au cas déterministe. Le solveur de Gurobi, le recuit simulé (SA), l’algorithme de chauve-souris, l’algorithme de luciole ont été proposés pour résoudre le modèle déterministe pour 56 instances respectivement. Enfin, le SA a été adopté pour traiter le modèle SPR. Une comparaison entre les solutions obtenues par les deux modèles a également été réalisée pour mettre en évidence la prise en compte des temps de parcours et de service stochastiques.(3) Pour garantir la qualité du service, sur la base d’un budget de la théorie de l’incertitude, nous avons proposé un modèle d’optimisation robuste (RO) pour HHC Routing, prenant en compte les exigences en termes de temps de déplacement et de service. La vérification de la solution réalisable a été réécrite en tant que fonction récursive complexe. Recherche tabou, SA, Recherche de voisinage variable sont également adaptés pour résoudre le modèle. Un grand nombre d'expériences ont été réalisées pour évaluer le modèle déterministe et le modèle RO. Une analyse de sensibilité des paramètres a également été effectuéeHome health care (HHC) is a wide range of healthcare services that can be given in one's home for an illness or injury. In recent years, the healthcare industry has become one of the largest sectors of the economy in developed countries. One of the most significant challenges in HHC domain is to assign the labor resources and equipment more efficiently under limited resources. Since the transportation cost is one of the most critical spendings in the company activities, it is of great significance to optimize the vehicle routing problem for HHC companies.However, a majority of the existing work only considers the deterministic model. In the practical of HHC, the decision-makers and caregivers often encounter with uncertainties. So, it is essential to incorporate the uncertainty into the model to make a reasonable and robust schedule for HHC company. This thesis addresses the HHC routing and scheduling problem with taking into account the non-deterministic demand, uncertain service and travel time respectively. The main body the thesis is composed of three independent works.(1) Based on the Fuzzy Credibility Theory, we proposed a fuzzy chance constraint programming (FCCP) model for HHC routing problem with fuzzy demand. This model has both characteristics of combinatorial optimization and FCCP. To deal with the large-scale problem, we developed a Hybrid Genetic Algorithm with the Monte Carlo simulation. Three series of experiments were conducted to validate the performance of the proposed model and algorithm. At last the sensitivity analysis was also carried out the observe the variable parameter involved in the fuzzy decision-making.(2) According to the activity of the caregivers in HHC, we proposed a two-stage stochastic programming model with recourse (SPR) for the simultaneous delivery and pick-up with stochastic travel and service times in HHC. To solve the model, firstly, we reduced the model to the deterministic one. Gurobi Solver, Simulated Annealing (SA), Bat Algorithm (BA), Firefly Algorithm (FA) were proposed to solve the deterministic model for 56 instances respectively. At last the SA was adopted to address the SPR model. Comparison between the solutions obtained by the two models was also conducted to highlight the consideration of the stochastic travel and service times.(3) To guarantee the service quality, based on a budget of uncertainty theory, we proposed a Robust Optimization (RO) model for HHC Routing with considering skill requirements under travel and service times uncertainty. The feasible solution check was rewritten as a complex recursive function. Tabu Search, SA, Variable Neighborhood Search are adapted to solve the model. A large number of experiments had been performed to evaluate the deterministic model and the RO model
16
Manasanan, Titapunyapat. „A GENETIC APPROACH FOR TWO-ECHELON CAPACITATED VEHICLE ROUTING AND SCHEDULING PROBLEM WITH TIME WINDOWS“. 京都大学 (Kyoto University), 2015. http://hdl.handle.net/2433/202695.
Der volle Inhalt der Quelle
17
Mohammed, Al-Yakoob Salem. „Mixed-Integer Mathematical Programming Optimization Models and Algorithms For An Oil Tanker Routing and Scheduling Problem“. Diss., Virginia Tech, 1997. http://hdl.handle.net/10919/30368.
Der volle Inhalt der QuelleAnnotation:
This dissertation explores mathematical programming optimization models and algorithms for routing and scheduling ships in a maritime transportation system. Literature surveyed on seaborne transportation systems indicates that there is a scarcity of research on ship routing and scheduling problems. The complexity and the overwhelming size of a typical ship routing and scheduling problem are the primary reasons that have resulted in the scarcity of research in this area.
The principal thrust of this research effort is focused at the Kuwait Petroleum Corporation (KPC) Problem. This problem is of great economic significance to the State of Kuwait, whose economy has been traditionally dominated to a large extent by the oil sector. Any enhancement in the existing ad-hoc scheduling procedure has the potential for significant savings.
A mixed-integer programming model for the KPC problem is constructed in this dissertation. The resulting mathematical formulation is rather complex to solve due to (1) the overwhelming problem size for a typical demand contract scenario, (2) the integrality conditions, and (3) the structural diversity in the constraints. Accordingly, attempting to solve this formulation for a typical demand contract scenario without resorting to any aggregation or partitioning schemes is theoretically complex and computationally intractable.
Motivated by the complexity of the above model, an aggregate model that retains the principal features of the KPC problem is formulated. This model is computationally far more tractable than the initial model, and consequently, it is utilized to construct a good quality heuristic solution for the KPC problem.
The initial formulation is solved using CPLEX 4.0 mixed integer programming capabilities for a number of relatively small-sized test cases, and pertinent results and computational difficulties are reported. The aggregate formulation is solved using CPLEX 4.0 MIP in concert with specialized rolling horizon solution algorithms and related results are reported. The rolling horizon solution algorithms enabled us to handle practical sized problems that could not be handled by directly solving the aggregate problem.
The performance of the rolling horizon algorithms may be enhanced by increasing the physical memory, and consequently, better solutions can be extracted. The potential saving and usefulness of this model in negotiation and planning purposes strongly justifies the acquisition of more computing power to tackle practical sized test problems.
An ad-hoc scheduling procedure that is intended to simulate the current KPC scheduling practice is presented in this dissertation. It is shown that results obtained via the proposed rolling horizon algorithms are at least as good, and often substantially better than, results obtained via this ad-hoc procedure.Ph. D.
18
Braekers, Kris, Richard F. Hartl, Sophie Parragh und Fabien Tricoire. „A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience“. Elsevier, 2016. http://dx.doi.org/10.1016/j.ejor.2015.07.028.
Der volle Inhalt der QuelleAnnotation:
Organizations providing home care services are inclined to optimize their activities in order to meet the constantly increasing demand for home care. In this context, home care providers are confronted with multiple, often conflicting, objectives such as minimizing their operating costs
while maximizing the service level offered to their clients by taking into account their preferences. This paper is the first to shed some light on the trade-off relationship between these two objectives by modeling the home care routing and scheduling problem as a bi-objective problem. The proposed model accounts for qualifications, working regulations and overtime costs of the nurses, travel costs depending on the mode of transportation, hard time windows, and client preferences on visit times and nurses. A distinguishing characteristic of the problem is that the scheduling problem for a single route is a biobjective problem in itself, thereby complicating the problem considerably. A metaheuristic algorithm, embedding a large neighborhood search heuristic in a multi-directional local search framework, is proposed to solve the problem.
Computational experiments on a set of benchmark instances based on reallife data are presented. A comparison with exact solutions on small instances shows that the algorithm performs well. An analysis of the results reveals that service providers face a considerable trade-off between costs and client convenience. However, starting from a minimum cost solution, the average service level offered to the clients may already be improved drastically with limited additional costs. (authors' abstract)
19
Qureshi, Ali Gul. „A COLUMN GENERATION BASED EXACT SOLUTION FOR VEHICLE ROUTING AND SCHEDULING PROBLEM WITH SOFT TIME WINDOWS“. 京都大学 (Kyoto University), 2008. http://hdl.handle.net/2433/124490.
Der volle Inhalt der Quelle
20
Dahal, Keshav P., Stephen M. Remde, Peter I. Cowling und N. J. Colledge. „Improving metaheuristic performance by evolving a variable fitness function“. Springer Verlag, 2008. http://hdl.handle.net/10454/2498.
Der volle Inhalt der QuelleAnnotation:
In this paper we study a complex real world workforce scheduling
problem. We apply constructive search and variable neighbourhood search
(VNS) metaheuristics and enhance these methods by using a variable fitness
function. The variable fitness function (VFF) uses an evolutionary approach to
evolve weights for each of the (multiple) objectives. The variable fitness
function can potentially enhance any search based optimisation heuristic where
multiple objectives can be defined through evolutionary changes in the search
direction. We show that the VFF significantly improves performance of
constructive and VNS approaches on training problems, and ¿learn¿ problem
features which enhance the performance on unseen test problem instances.
21
Sze, San Nah. „A study on multi-trip vehicle routing problem with time windows and meal break considerations“. Thesis, The University of Sydney, 2011. http://hdl.handle.net/2123/7746.
Der volle Inhalt der QuelleAnnotation:
In the manpower scheduling problem with multiple trips vehicle routing and time windows consideration, a group of staff workers has to be assigned to a number of jobs in such a way that the total number of staff required is minimised, and each job’s requirements for manpower, transportation time, and time windows must be respected. Furthermore, if several staff is requested to cooperate, they must work on the job at the same time. The problem originates from manpower scheduling for the in-flight food loading operations and could be modeled as Multiple Trips Vehicle Routing and Scheduling Problem with Time Windows and meal break considerations (MTVRSPTW-MB). In this thesis, we present a mathematical model of MTVRSPTW-MB and show that even for a reduced problem; it is intractable on this small sample size of data. Therefore, we developed an original two-stage scheduling heuristic algorithm to cope with this complicated combinatorial optimisation problem. This heuristic uses some simple laxity scheduling and priority rules to do the job assignment and scheduling in two stages. The heuristic is tested on real-life problem instances supplied by one of the in-flight caterers from Malaysia. On top of that, a pre-processing data algorithm was developed to spread the demand as evenly as possible. We obtained excellent solutions in reduction manpower in all the cases within three seconds. We also evaluated the heuristic further by comparing it with a popular heuristic insertion algorithm. The computational results report the effectiveness and robustness of our proposed heuristics. Our heuristic algorithm has also proved computational bounded.
22
Moussavi, Seyed Esmaeil. „Workforce scheduling and job rotation by considering ergonomic factors (Presentation of the Sequencing Generalized Assignment Problem) : application to production and home healthcare systems“. Thesis, Bourgogne Franche-Comté, 2018. http://www.theses.fr/2018UBFCA017/document.
Der volle Inhalt der QuelleAnnotation:
Cette thèse porte sur la planification du personnel en accordant une attention particulière à l'aspect humain et aux facteurs ergonomiques dans le domaine de la production. Un certain nombre de modèles mathématiques sont présentés pour formuler les problèmes d'ordonnancement et de planification du personnel étudié. Concernant les modèles de planification, la productivité du système de fabrication et le bien-être des travailleurs sont ciblés. De cette manière, une méthode d'affectation des travailleurs est présentée pour réduire le temps de production et une méthode d'ordonnancement pour la rotation des tâches est présentée afin d’équilibrer la charge de travail des opérateurs. À cet effet, une analyse ergonomique est effectuée sur les postes de travail du système de production étudié. Cette analyse aboutit à l'évaluation des postes du travail suivant la convention dite des feux de circulation, c'est-à-dire que les postes sont classés dans les niveaux de charge faible, moyen et élevé qui sont représentés respectivement par les couleurs verte, jaune et rouge. Une approche mathématique est développée pour convertir ces résultats en valeurs numériques, car les paramètres quantitatifs sont plus applicables pour l'optimisation de la planification. Une programmation multi-objectifs est proposée pour optimiser les deux objectifs mentionnés du problème d'ordonnancement de tournée du personnel étudié. Les méthodes d'agrégation linéaire et de ε-contrainte sont appliquées pour résoudre ce modèle d'optimisation. En outre, cette thèse présente une nouvelle variante du problème d'affectation appelé problème d'affectation généralisée par séquence qui est défini pour la planification du personnel dans un système combiné constitué des postes de travail en série et en parallèle. Il est prouvé que ce problème d'optimisation combinatoire est NP-difficile et les méthodes exactes ne sont pas capables de résoudre les instances de grande taille. Ainsi, trois méthodes approchées composées de deux approches matheuristiques et une heuristique hybride sont développées pour résoudre ce problème. Les méthodes matheuristiques sont basées sur la décomposition de la formulation pour simplifier le modèle principal en deux ou plusieurs modèles plus petits. La troisième méthode est une heuristique gloutonne combinée à une recherche locale. En outre, dans la dernière étape de cette thèse, la planification des ressources humaines pour un système de soins à domicile est formulée mathématiquement. Selon la structure du système, une intégration des problèmes d'affectation et de tournées de véhicules est présentée. Enfin, une approche matheuristique en trois étapes est proposée pour résoudre ce problème d'optimisation combinatoireThis thesis concerns the human resource planning by paying a special attention to the human aspect and ergonomic factors in the manufacturing domain. A number of mathematical models are presented to formulate the studied workforce scheduling and planning problems. In the planning models, the productivity of the manufacturing system and the well-being of the workers are targeted. In this way, a worker assignment approach is presented to reduce the production time and a job rotation scheduling approach is presented to balance the workloads on the operators. For this purpose, an ergonomic analysis is carried out on the jobs of the studied production system. This analysis results in the traffic light evaluation for the jobs, i.e., the jobs are categorized into the low, medium and high workload levels which are presented respectively by the green, yellow and red colors. A mathematical approach is developed to convert these outputs to the numerical values, because the quantitative parameters are more applicable for the optimization of the planning. A multi-objective programming is proposed to optimize two mentioned objectives of the studied workforce scheduling problem. Both linear aggregation and epsilon-constraint methods are applied to solve this optimization model. Furthermore, this thesis presents a novel variant of the assignment problem called sequencing generalized assignment problem which is defined for workforce scheduling in a combined system consisting of the jobs in series and in parallel. It is proved that this combinatorial optimization problem is NP-hard and the exact methods are not able to solve the large-scale instances. Hence, three approximate methods consisting of two matheuristic and a hybrid heuristic approaches are developed to solve it. The matheuristic methods are based on the decomposition of the formulation to break down and simplify the main model into two or more smaller models. The third method is a greedy heuristic combined with a local search. The efficiency of the three mentioned methods is evaluated by various instances of different sizes. Moreover, in the last step of this thesis, the human resource planning for a home healthcare system is formulated mathematically. According to the structure of the system, an integration of the worker assignment and vehicle routing problems is presented. Finally, a three-steps matheuristic approach is proposed to solve this combinatorial optimization problem
23
Bhusiri, Narath. „EXACT SOLUTIONS FOR VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH FULL SOFT TIME WINDOWS USING COLUMN GENERATION AND LABELING ALGORITHMS“. 京都大学 (Kyoto University), 2013. http://hdl.handle.net/2433/180484.
Der volle Inhalt der Quelle
24
Aguayo, Bustos Maichel Miguel. „Modeling, Analysis, and Exact Algorithms for Some Biomass Logistics Supply Chain Design and Routing Problems“. Diss., Virginia Tech, 2016. http://hdl.handle.net/10919/81878.
Der volle Inhalt der QuelleAnnotation:
This dissertation focuses on supply chain design and logistics problems with emphasis on biomass logistics and routing problems. In biomass logistics, we have studied problems arising in a switchgrass-based bio-ethanol supply chain encountered in the Southeast, and a corn stover harvest scheduling problem faced in the Midwest Unites States, both pertaining to the production of cellulosic ethanol. The main contributions of our work have been in introducing new problems to the literature that lie at the interface of the lot-sizing and routing problems, and in developing effective exact algorithms for their solution.
In the routing area, we have addressed extensions of the well-known traveling salesman and vehicle routing problems. We have proposed new formulations and have developed exact algorithms for the single and multiple asymmetric traveling salesmen problems (ATSP and mATP), the high-multiplicity asymmetric traveling salesman problem (HMATSP) and its extensions, and the fixed-destination multi-depot traveling salesman problem with load balancing (FD-MTSPB). Furthermore, we have introduced a new strategy to reduce routing cost in the classical vehicle routing problem (VRP).Ph. D.
25
Daniel, Aang. „Routing and Scheduling with Time Windows: Models and Algorithms for Tramp Sea Cargos and Rail Car-Blocks“. Diss., Atlanta, Ga. : Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/19698.
Der volle Inhalt der QuelleAnnotation:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007.Committee Chair: Al-Khayyal, Faiz; Committee Member: Barnes, Earl; Committee Member: Johnson, Ellis; Committee Member: Karimi, IA; Committee Member: Sokol, Joel.
26
Afroze, Tonima, und Gardell Moa Rosén. „Algorithm Construction for Efficient Scheduling of Advanced Health Care at Home“. Thesis, KTH, Skolan för teknik och hälsa (STH), 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-170392.
Der volle Inhalt der QuelleAnnotation:
Providing advanced health care at home rather than in a hospital creates a greater quality of life for patients and their families. It also lowers the risk of hospital-acquired infections and accelerates recovery. The overall cost of care per patient is decreased. Manual scheduling of patient visits by health care professionals (HCPs) has become a bottleneck for increased patient capacity at SABH, a ward providing advanced pediatric health care at home (“Sjukhusansluten Avancerad Barnsjukvård i Hemmet” in Swedish), since many parameters need to be taken into account during scheduling. This thesis aims to increase the efficiency of SABH’s daily scheduling of personnel and resources by designing an automated scheduler that constructs a daily schedule and incorporates changes in it when needed in order to remove scheduling as a limitation for increased patient capacity. Requirements on a feasible schedule are identified in cooperation with SABH and literature is investigated about similar areas where the scheduling process has been automated. The scheduling is formulated as a computerized problem and investigated from the perspective of theoretical computer science. We show that the scheduling problem is NP-hard and can therefore not be expected to be solved optimally. The algorithm for scheduling the visits minimizes violations of time windows and travel times, and maximizes person continuity and workload balancing. The algorithm constructs an initial solution that fulfills time constraints using a greedy approach and then uses local search, simulated annealing, and tabu search to iteratively improve the solution. We present an exact rescheduling algorithm that incorporates additional visits after the original schedule has been set. The scheduling algorithm was implemented and tested on real data from SABH. Although we found the algorithm to be efficient, automatic transfer of data from the patient journal system is an imperative for the scheduler to be adopted.Barn som får avancerad sjukvård hemma istället för på sjukhus tillfrisknar ofta snabbare och risken för vårdrelaterade infektioner minskar. Barnen och deras familjer blir mer välmående av att få vistas i sin hemmiljö. På Astrid Lingrens barnsjukhus i Stockholm erbjuds avancerad hemsjukvård av avdelningen Sjukhusansluten Avancerad Barnsjukvård i Hemmet (SABH). För att schemalägga när patienterna ska besökas av sjukvårdspersonalen behöver många olika faktorer beaktas, detta sker idag helt manuellt. Den manuella schemaläggningen utgör en naturlig begränsning av SABHs patientkapacitet. Denna uppsats syftar till att effektivisera schemaläggningsprocessen hos SABH genom att föreslå en automatiserad lösning som hanterar koordinering av personal och resurser och dem förändringar som behöver göras i schemat under dagen, för att få bort schemaläggningsprocessen som ett hinder mot ökad patientkapacitet. Krav på schemaläggningen identifieras i diskussion med SABH och genom att studera litteratur kring liknande områden där schemaläggning lösts automatiserat. Vi formulerar schemaläggningen som ett datologiskt problem och analyserar det med utgångspunkt i teoretisk datalogi. Vi visar att problemet är NP-svårt och därför inte kan förväntas lösas optimalt inom rimlig tid. Vår lösning approximerar istället fram ett rimligt svar, där fokus hos algoritmen är att patienterna ska besökas de tider de behöver, personalens restider ska vara så korta som möjligt samtidigt som arbetsbördan hos personalen ska vara så lika fördelad som möjligt och patienterna ska, i den mån det är möjligt, få vård av samma personal. Med en girig algoritm konstrueras ett initialt schema som uppfyller de grundläggande kraven, detta schema förbättras med lokalsökning, simulated annealing och tabusökning. En exakt lösning framställs för uppdatering av schemat. Algoritmen för att lägga ett dagligt schema (utan uppdateringar) implementerades och testades med riktigt data från SABH. Vår algoritm visade sig vara effektiv, men för att kunna göra hela schemaläggningsprocessen effektiv behöver den integreras med journalsystemet.
27
Avila, Narvaez Juan Agustin, und Salas Leonardo Abad Barriga. „Propuesta de mejora para reducir los tiempos de retraso en proyectos eléctricos en baja tensión para una empresa de servicios localizada en Lima aplicando Last Planner System, Vehicle Routing Problem y Workforce Management“. Bachelor's thesis, Universidad Peruana de Ciencias Aplicadas (UPC), 2019. http://hdl.handle.net/10757/651573.
Der volle Inhalt der QuelleAnnotation:
El presente estudio versa sobre la ejecución proyectos eléctricos en baja tensión, los cuales son ejecutados por una empresa de servicios cuyas operaciones se realizan en Lima.
El capítulo 1 presenta la literatura asociada a la solución del problema, en donde se desarrolla el marco teórico de las metodologías propuestas. El capítulo 2 muestra el uso de las herramientas de la ingeniería industrial a efectos de identificar el problema: “retrasos en la ejecución de proyectos de baja tensión con reforma”. Esta problemática genera una pérdida anual de 381 miles de soles y un déficit de capital de trabajo de 11,500 miles de soles correspondiente al año 2017.
El capítulo 3 plantea la solución de la problemática expuesta, para lo cual se definen dos etapas. La primera permite la eliminación del backlog acumulado hasta el mes de setiembre de 2018. La segunda se refiere al desarrollo de las metodologías: Last Planner System, Vehicle Routing Problem y Workforce Management.
En el capítulo 4 se realiza la validación de las propuestas de las mejoras planteadas. En la primera etapa se contrataron 210 personas para eliminar el backlog y se validó una utilidad de 104 miles de soles. Para la segunda etapa, se implementó el proyecto cuadrillas propias y se utilizaron las metodologías Last Planner System y Vehicle Routing Problem.. Finalmente, se integró ambas metodologías con la incorporación de tecnología del tipo Workforce Management. Los resultados muestran una TIR del 20% y un VAN de 229 miles de soles.The present research is about the implementation of low voltage electrical projects, which are performed by an utility company whose area of operations is the city of Lima. Chapter 1 describes the literature associated with the solution of the problem, where the theoretical framework of the above mentioned methodologies is developed. Chapter 2 describes the results obtained through the utilization of industrial engineering tools, with which the problem is identified as: "delays in the implementation of low voltage projects with reform". This problem generates an annual loss of 381 thousand soles and a working capital deficit of 11,500 thousand soles corresponding to year 2017. Chapter 3 proposes the solution of the exposed problem, for which two stages are defined. The first one allows the elimination of the accumulated backlog until September 2018. The second one refers to the development of the methodologies: Last Planner System, Vehicle Routing Problem and Workforce Management. Chapter 4 validates the proposed improvements. In the first stage, 210 people were hired to eliminate the backlog and as a result there was a profit of 104 thousand soles for the period within July and September. For the second stage, the project of own crews was implemented and there were used Last Planner System and the Vehicle Routing Problem as methodologies in order to optimize the route of the crews. Finally, both methodologies were integrated with the incorporation of the Workforce Management technology. The results show an IRR of 20% and a NPV of 229 thousand soles.
Trabajo de Suficiencia Profesional
28
Williams, Matthew J. „A Heuristic Solution to the Pickup and Delivery Problem with Applications to the Outsized Cargo Market“. Ohio University / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1238514369.
Der volle Inhalt der Quelle
29
Gondran, Matthieu. „Problèmes d'ordonnancement et de moyens de transport des systèmes de production : prise en compte de la qualité de service“. Thesis, Université Clermont Auvergne (2017-2020), 2019. http://www.theses.fr/2019CLFAC037/document.
Der volle Inhalt der QuelleAnnotation:
Ce manuscrit aborde des problèmes d’ordonnancement et de transport avec une modélisation explicite du transport. De tels problèmes se modélisent communément sous forme de graphes qui sont évalués afin d’obtenir les dates de début des opérations.Les évaluations classiques des graphes sont effectuées au moyen d’algorithmes de plus long chemin permettant d’obtenir une solution semi-active, où toutes les dates des opérations sont au plus tôt. Néanmoins, ces évaluations permettent généralement de ne prendre en compte que des critères de temps ou de distance à minimiser. Les travaux présentés dans ce manuscrit proposent de tenir compte de critères de qualité de service dans la fonction objectif. Cette prise en considération nécessite de nouvelles fonctions d’évaluation du graphe afin d’obtenir des solutions non nécessairement semi-actives permettant de maximiser la qualité de service. En effet, une solution semi-active propose rarement une qualité de service optimale. Les critères de qualité de service adoptés portent sur les ordonnancements et sur le transport.Trois problèmes intégrés sont successivement traités. Le premier problème est un problème de Job-shop avec transport et qualité de service, appelé Job-shop Scheduling Problem with Routing (JSPR). Des pièces, définies par une succession d’opérations, sont à fabriquer sur différentes machines, et entre deux opérations, la pièce doit être transportée de machine en machine. Le critère de qualité de service dans ce problème est dépendant des délais entre, d’une part les différentes opérations sur les machines, et d’autre part entre les différentes opérations de transport. Les gammes opératoires et les opérations de transport sont dépendantes les unes des autres.Le second problème est un problème de Workforce Scheduling and Routing Problem (WSRP), assimilable à un problème de planification de visites à domicile par un ensemble d’employés, et où le transport est pris en compte. Pour ce problème, le critère de qualité de service dépend des dates de début des visites. Les tournées sont indépendantes les unes des autres.Le troisième problème est le Generalised Workforce Scheduling and Routing Problem (GWSRP), qui prend en compte des contraintes de coordination entre les employés. Les tournées de ces derniers sont dépendantes les unes des autres. Elles nécessitent d’être toutes considérées simultanément pour évaluer les dates des visites respectant les contraintes de coordination et maximisant la qualité de service.Pour chaque problème, une nouvelle fonction d’évaluation est proposée. Pour le JSPR, cette fonction est basée sur l’algorithme de (Cordeau and Laporte, 2003) qui est initialement prévu pour le Dial-A-Ride Problem, ainsi que sur l’insertion de time-lags dans le graphe disjonctif du JSPR. Cette évaluation est incluse dans une métaheuristique. Pour le WSRP, la fonction d’évaluation est basée sur un algorithme de calcul du plus court chemin avec un algorithme de type programmation dynamique à labels. Elle est généralisée pour être utilisée dans une génération de colonnes. Et enfin, pour le GWSRP, l’évaluation est effectuée par un modèle PPC qui combiné à une génération de colonnes définissent tous deux un schéma d’optimisation globalThis manuscript addresses scheduling and transport problems where the transport is explicitly taken into account. Such problems are commonly modelled by graphs that are evaluated to obtain the starting times of operations.Classic graph evaluations are performed using longer path algorithms to obtain a semi-active solution, where all operations are left shifted. Nevertheless, these evaluations generally allow only time or distance criteria to be taken into account. The work presented in this thesis propose to take the quality of service criteria into account in the objective function. These considerations require new graph evaluation functions in order to obtain non-semi-active solutions that maximise the quality of service. Indeed, a semi-active solution rarely offers maximum quality of service. Three integrated problems are successively addressed. The first problem is a Job-shop Scheduling Problem with transport and quality of service, referred to as Job-shop Scheduling Problem with Routing (JSPR). Jobs, defined by a succession of operations, are to be performed on different machines, and between two operations, the job must be transported from a machine to another machine. The quality of service criterion in this problem depends on the delay between, on the one hand, the different operations belonging to the same job, and on the other hand, between the different transport operations. Machine-operations and transport-operations are dependent.The second problem is a Workforce Scheduling and Routing Problem (WSRP), which is similar to a problem of planning home services by a set of employees, and where transport is taken into account. For this problem, the quality of service criterion depends on the starting times of the visits. The trips of employees are independent.The third problem is the Generalised Workforce Scheduling and Routing Problem (GWSRP), which takes coordination constraints between employees into account. The trips are dependent on each other. The evaluation function of the starting times must consider simultaneously all trips in order to respect all coordination constraints and to maximise the service quality.For each problem, a new evaluation function is proposed. For the JSPR, this function is based on the algorithm of (Cordeau and Laporte, 2003) which is introduced first for the Dial-A-Ride Problem. The evaluation function, for the JSPR, is based on the insertion of time-lags in the disjunctive graph. This evaluation is included in a metaheuristic. For the WSRP, the evaluation function is based on the dynamic labelling algorithm used for an Elementary Shortest Path Problem With Resource Constraints. This function is generalised in order to be included in a column generation scheme. Finally, for the GWSRP, the evaluation is performed by a PPC model combined with a generation of columns and both define an overall optimisation scheme
30
Junqueira, Rogério de Ávila Ribeiro. „Programação das frentes de colheita de cana-de-açúcar: uma modelagem visando o equilíbrio das capacidades de colheita e transporte“. Universidade Federal de São Carlos, 2014. https://repositorio.ufscar.br/handle/ufscar/3449.
Der volle Inhalt der QuelleAnnotation:
Made available in DSpace on 2016-06-02T19:50:25Z (GMT). No. of bitstreams: 1
6346.pdf: 5901404 bytes, checksum: 2d78b0f5f68ac25a089acd315f55b157 (MD5)
Previous issue date: 2014-06-09The production of sugar, ethanol and electricity from sugar cane necessarily involves harvesting and transportation of raw materials, which are expensive and complex operations and have significant influence on the quality of the industrial raw material. The literature reports several optimization approaches related to the planning of planting, harvesting and transporting of sugarcane, however the scheduling of harvesting fronts is underexplored. This thesis intends to contribute to the state-of-art of this important issue in the context of the Brazilian agribusiness. Optimization approaches to support scheduling decisions of harvesting fronts considering the balance of harvesting and transportation capacities, as well as good agronomic management are proposed. The approaches are inspired by the representation of the problem as a lot sizing and scheduling model with parallel machines and sequence-dependent setup costs and times, a modelling technique well studied in the production planning and control literature. Three variants of this formulation, based on mathematical programming models, were developed and tested in two real case studies of medium size sugar mills. Heuristic methods based on aggregation procedures and mathematical programming have also been studied and developed to solve large scaled problems found in practice. Among the three variants studied, one presented the best solution quality within the expected execution time. Important scenario analysis were done indicating that the schedule s fulfilment provides reduction of harvesting and transporting complexity to the following season, which can generate significant saves in the cases studied. Besides that, comparing the proposed scheduling method with one of the sector s practice, it can be generated also significant cost reduction in the cases studied. The results were analyzed according to a validation methodology (descriptive facet of tetraedrum) well known in the literature.
A produção de açúcar, álcool e energia elétrica a partir de cana-de-açúcar passa necessariamente pela colheita e transporte da matéria-prima, que são operações custosas, complexas e que interferem significativamente na qualidade da matéria-prima industrial. A literatura reporta várias abordagens de otimização relacionadas ao planejamento do plantio, da colheita e do transporte de cana-de-açúcar, todavia a programação das frentes de colheita é pouco explorada. Nesta tese pretende-se contribuir para o estado da arte deste importante tema no contexto do agronegócio brasileiro. Propõe-se abordagens de otimização para apoiar decisões de programação das frentes de colheita, considerando-se o equilíbrio das capacidades de colheita e transporte, bem como um bom manejo agronômico. As abordagens são inspiradas na representação do problema por meio de um modelo de dimensionamento de lotes e sequenciamento da produção em máquinas paralelas com custos e tempos de setup dependentes da sequência, bem estudado na literatura em contextos de planejamento e controle da produção. Para isso foram desenvolvidas três variantes desta formulação baseadas em programação matemática, voltadas para a programação das frentes de colheita, que foram testadas em dois estudos de caso reais de usinas de cana-de-açúcar de médio porte do setor. Métodos heurísticos baseados em procedimentos de agregação e programação matemática também foram estudados e desenvolvidos para a resolução dos problemas de grande porte encontrados na prática. Das três variantes estudadas, uma delas apresentou melhor qualidade da solução dentro de tempos computacionais aceitáveis para o problema. Análises de cenário importantes foram feitas indicando que o cumprimento da programação proporciona redução de complexidade da colheita e transporte na safra seguinte, podendo gerar economias significativas nos casos estudados. Além disso, a comparação dos resultados das abordagens aqui exploradas com o que é praticado no setor indica um potencial de redução de custos também significativo para os casos estudados. Os resultados foram analisados de acordo com uma metodologia de validação (faceta descritiva do tetraedro) conhecida na literatura.
31
Zheng, Yahong. „Supply chain management under availability & uncertainty constraints“. Thesis, Ecole centrale de Lille, 2012. http://www.theses.fr/2012ECLI0019/document.
Der volle Inhalt der QuelleAnnotation:
Le management de la chaîne logistique concerne un large éventail d’activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l’incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l’incertitude, l’indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d’incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d’aborder ce problème d’une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l’incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d’incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L’incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décisionSupply chain management involves a wide range of activities. Among most of them, uncertainty exists inherently and always brings some consequence not expected. However, uncertainty is not considered much in conventional supply chain management. In the case where availability of resources is not what we expect, complexity of supply chain management increases. Taking constraints of uncertainty and availability into account, we aim to discuss supply chain management from different aspects. This thesis is an attempt of systematic and complete research from this point and we would like to offer some references to researchers and managers in supply chain. We focus on three classic sources of uncertainty: demand, manufacturing and distribution. For each source of uncertainty, we analyze its cause and its impact to the performance of the supply chain. Uncertainty is specified into concrete classic problem and an approach is proposed to solve it. Furthermore, bi-level newsboy problem as a miniature of supply chain, is focused under double uncertain environment. Treating uncertain variables is actually a treatment on operational level. The methods used offer good demonstration in treating uncertain variables in decision problems
32
Furtado, Maria Gabriela Stevanato. „O problema de roteamento e programação de navios com coleta e entrega na indústria de petróleo : modelagem e métodos de solução exatos“. Universidade Federal de São Carlos, 2016. https://repositorio.ufscar.br/handle/ufscar/8486.
Der volle Inhalt der QuelleAnnotation:
Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-24T10:38:55Z
No. of bitstreams: 1
TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5)Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:50:29Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5)
Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:51:23Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5)
Made available in DSpace on 2017-02-08T10:51:33Z (GMT). No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) Previous issue date: 2016-04-01
Outra
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
The object of this study is the routing and scheduling problem of vessels with pickup and delivery and time windows in the oil industry. A case study was performed in a Brazilian oil industry that produces crude oil in o shore platforms, that is, located in the ocean, and transports to the terminals located in the Brazilian coast. Then, it was proposed a mixed integer model to represent the problem adequately and for this, a detailed analysis of the real problem in order to know all its characteristics and consider some simplifying assumptions. Therefore, to the pickup and delivery problem with time windows present in the literature were aggregated other speci c restrictions of the case study, for example, multiple depots, ship mooring restrictions, exible draft and dynamic positioning. Besides that, the eet is heterogeneous related to capacity, LOA (length overall), dynamic positioning and velocity. In practice, in general there are no identical vessels. This problem can be represented as a combinatorial optimization model, which belongs to the NP-hard class and its solution is a challenging in practice depending on the size of the real problems. Then, were proposed several exact branch-and-cut methods based on models with 2 and 3-index variables for routing problems with pickup and delivery and time windows to solve speci cally the Brazilian oil industry problem. Finally, we proposed a branch-and-price method, which includes all characteristics of the problem in oil industry. In summary, the main contributions of this thesis are related to the study and modeling of this problem in practice, and the proposal and development of exact solution methods to solve it, based on branch-and-cut and branch-and-price. The performance of the mathematical model in optimization software and the exact methods were veri ed using a real data set provided by the company. Results show that these approaches may be e ective to solve problems of moderate size in real situations.
O objeto de estudo deste trabalho é o problema de roteamento e programação de navios com coleta e entrega e janelas de tempo na indústria petrolífera. Foi realizado um estudo de caso com uma empresa petrolífera brasileira que produz óleo cru em plataformas o shore, isto é, localizadas no oceano e os transporta até os terminais localizados na costa brasileira. Então, foi proposto um modelo de programação inteira mista para representar o problema adequadamente e para isso, foi necessária uma análise detalhada do problema real, com o intuito de conhecer todas as suas características e considerar hipóteses simpli cadoras. Desta maneira, ao problema de coleta e entrega e janelas de tempo da literatura foram agregadas outras restrições especí cas do problema do estudo de caso como, por exemplo, múltiplos depósitos, restrições de atracação dos navios, calado exível e posicionamento dinâmico. Além disso, a frota de navios é heterogênea em relação à capacidade, LOA (length overall ), posicionamento dinâmico e velocidade. Na prática, em geral não existem navios iguais. Este problema pode ser representado como um modelo de otimização combinatória que pertence à classe NP-difícil e sua solução é bastante desa adora na prática em função do tamanho dos problemas reais. Depois, foram propostos vários métodos do tipo branch-and-cut baseados em modelos com variáveis de 2 e 3-índices para problemas de roteamento com coleta e entrega e janelas de tempo para resolver especi camente o problema da empresa brasileira. E por m, foi proposto um método do tipo branch-and-price, o qual abrange todas as características do problema da indústria petrolífera. Em síntese, as principais contribuições desta tese referem-se ao estudo e modelagem deste problema na prática, e a proposta e desenvolvimento de métodos de solução exatos para resolvê-lo, baseados em branch-and-cut e branch-and-price. O desempenho do modelo matemático em softwares de otimização e também dos métodos exatos propostos foi veri cado usando-se exemplares reais fornecidos pela empresa. Os resultados mostram que essas abordagens podem ser efetivas para resolver problemas de tamanho moderado em situações reais.
33
Huang, Li-Fen, und 黃麗芬. „A vehicle routing and scheduling problem for a distribution center“. Thesis, 1998. http://ndltd.ncl.edu.tw/handle/49702202577431838863.
Der volle Inhalt der QuelleAnnotation:
碩士逢甲大學
工業工程研究所
86
In this Thesis, issues of vehicle routing and scheduling problem in a distribution center are addressed using optimization techniques. Due to the change of markets in terms of production, distribution, and marketing, a large number of distribution centers and the associated conveniences stores are established in the recent years. The distribution services of commodities provided from a distribution center to convenience stores are the most important issues, since these services have great impacts on the performance of a distribution center and on the customer service level. Hence, vehicle routing and scheduling problem are applied to improve the distribution service of goods. In this study, four alternative approaches are presented for the vehicle routing and scheduling problem. These approached are the savings method, the location- based method with heuristic for routing, the location-based method with the traveling salesman model for routing, and the optimization model simultaneously considering routing and clustering. A real-world data collected from a local distribution center are used to compare the performance of these approaches. Results indicate that the presented four alternative approached perform better than the current vehicle routing and scheduling system in terms of the total traveling distance and the balance of workloads. However, the CPU time needed to solve the real-world problem has to be shortened in order that the developedmodel can be used in the daily-based decision making process.
34
Hsu, Cheng-Liang, und 許正良. „Artificial Intelligence Approaches for the Home Care Scheduling Routing Problem“. Thesis, 2013. http://ndltd.ncl.edu.tw/handle/35yfze.
Der volle Inhalt der QuelleAnnotation:
碩士國立虎尾科技大學
工業工程與管理研究所
101
This thesis studies the home care scheduling routing problem which containes the arrangement of servers and periodic service locations. The objective of interest in this thesis is to minimize the total cost based upon the combination of types and number of servers and the service location scheduling. The home care scheduling routing problem is classified into the periodic vehicle routing problem (PVRP). Besides, due to the PVRP is essentially a NP-Hard problem, typical mathematical programming approaches are time consuming for finding the optimal solution of PVRP. Hence, In this study, heuristics are proposed to solve this home care scheduling routing problem. Although we cannot ensure to find the optimal solution, the proposed heuristics are able to obtain approximate optimal solutions fastly. In this study, we apply three heuristic algorithms, including Genetic Algorithm, Immune Algorithm and Particle Swarm Optimization. Based upon different service times, combinations of vehicles, speeds of service rate (SSR) and costs rate (SSC), we solve several home care scheduling routing problems and discuss the performance of these three heuristic algorithms. Numerical results indicate that the heuristic algorithms can find good solutions for the considered problems. In addition, numerical results also show that the proposed Immune Algorithm performs better than both Genetic Algorithm and Particle Swarm Optimization. Moreover, Genetic Algorithm is also performs better than Particle Swarm Optimization.
35
Yang, Tzong Ming, und 楊宗銘. „The Investigation of Scheduling Problem with Alternate Routing Using Genetic Algorithms“. Thesis, 1995. http://ndltd.ncl.edu.tw/handle/87854359772799006994.
Der volle Inhalt der Quelle
36
Joubert, Johannes Wilhelm. „An initial solution heuristic for the vehicle routing and scheduling problem“. Diss., 2004. http://hdl.handle.net/2263/27582.
Der volle Inhalt der QuelleAnnotation:
South Africa provides a fascinating interface between the developed and the developing world and poses a multitude of opportunities for enhancing the sustainable development of local cities. The concept of City Logistics is concerned with the mobility of cities, and entails the process of optimizing urban logistics activities by considering the social, environmental, economic, financial, and energy impacts of urban freight movement. Vehicle routing and scheduling has the potential to address a number of these key focus areas. Applying optimization to vehicle routing and scheduling results in a reduced number of trips, better fleet utilization, and lower maintenance costs; thereby improving the financial situation of the fleet owner. Improved fleet utilization could have a positive environmental impact, while also improving the mobility of the city as a whole. Energy utilization is improved while customer satisfaction could also increase through on-time deliveries and reliability. The Vehicle Routing Problem (VRP) is a well-researched problem in Operations Research literature. The main objective of this type of problem is to minimize an objective function, typically distribution cost for individual carriers. The area of application is wide, and specific variants of the VRP transform the basic problem to conform to application specific requirements. It is the view of this dissertation that the various VRP variants have been researched in isolation, with little effort to integrate various problem variants into an instance that is more appropriate to the South African particularity with regards to logistics and vehicle routing. Finding a feasible, and integrated initial solution to a hard problem is the first step in addressing the scheduling issue. This dissertation attempts to integrate three specific variants: multiple time windows, a heterogeneous fleet, and double scheduling. As the problem is burdened with the added constraints, the computational effort required to find a solution increases. The dissertation therefore also contributes to reducing the computational burden by proposing a concept referred to as time window compatibility to intelligently evaluate the insertion of customers on positions within routes. The initial solution algorithm presented proved feasible for the integration of the variants, while the time window compatibility decreased the computational burden by 25%, and as much as 80% for specific customer configurations, when using benchmark data sets from literature. The dissertation also improved the quality of the initial solution, for example total distance traveled, by 13%. Finding an initial solution is the first step in solving vehicle routing problems. The second step is to improve the initial solution iteratively through an improvement heuristic in an attempt to find a global optimum. Although the improvement heuristic falls outside the scope of this dissertation, improvement of the initial solution has a significant impact on the quality of improvement heuristics, and is therefore a valuable contribution.Dissertation (MEng)--University of Pretoria, 2007.
Industrial and Systems Engineering
MEng
Unrestricted
37
Gao, Bing-yu, und 高秉裕. „Integrated Production Scheduling and Vehicle Routing Problem to Minimize Total Cost“. Thesis, 2013. http://ndltd.ncl.edu.tw/handle/52860088294329155240.
Der volle Inhalt der QuelleAnnotation:
碩士國立雲林科技大學
工業工程與管理研究所碩士班
101
In the current the supply chain has many kinds of distribution center, and try their best to cost down; however they have many different kinds and also have different fitness strategies, not push-based Supply chain, but pull-based supply chain, and in the pull-based supply chain, how to respond they require is the most important point, and production scheduling and vehicle routing problem are concentrated by the research of the past, but most of them are considered separately; and there is some literature to integrate the production scheduling and vehicle routing problem, but all of the above are focus on how to combine the require and reduce the total deliver times, and the condition appears to the global supply chain or between locations; this research and the literature are different, and it’s appearing at the upward integration distribution center, and focus on how to reduce the vehicle operating cost, routing cost, and earliness, lateness cost. The research mainly discusses distribute in location, and integration production scheduling and vehicle routing problem; the environment considers a pull-based distribution, that is distribution center have multiple customers and requires are known, and objection is how to make the total cost to minimize.
38
Wang, Mu-Kung, und 王木坤. „A Study of The Vehicle Routing and Scheduling Problem Under Time Constraints“. Thesis, 1997. http://ndltd.ncl.edu.tw/handle/15312587805680675058.
Der volle Inhalt der QuelleAnnotation:
碩士中原大學
工業工程學系
85
Different from other businesses, the distribution center spends a lot on transportation cost. However, it is an important whether the distribution center gets increasement to reduce its transportation cost. In the past, the distribution center only considers the routing and vehicle scheduling problem for the transportation cost; Now, "Customers Are Always Right", One often claims to receive his demand on the special time interval; if not, One will refuse the service or will fine the distribution center, we call this "Time Windows Constraints". The transportation model becomes more complex with the constraint and hard to solve it. On the considerations of vehicle routing and time windows constraints, this research proposed three algorithms to reduce the transportation cost. Both "Minimize cost with equal-time interval" and "Minimize cost with fix three-points" do the routing first, then scheduling. The different between the two algorithm is that, the former decides the vehicle''s departure time for the first customer with the minimum cost, the latter consider minimum cost for every two customers, the "Minimum cost with group technology" will gather all customers into appropriate groups by their time window''s midpoint, then scheduling by one of the first two algorithms with the lower costs. Finally, this research will propose a algorithm simultaneously considering the distance and time windows based on the "Minimum cost with group technology", and compre the four algorithm with the point of view for the cost and distance. At the end of this research, we develop a new algorithm based on "Minimum cost with group technology", which both consider the routing and the scheduling. We call it "Minimum cost with dynamic group technology", and compare its performance with the other algorithms.
39
Chih, Kun-Lin, und 池昆霖. „A Study on Location Routing Problem and Production Scheduling for Perishable Goods“. Thesis, 2006. http://ndltd.ncl.edu.tw/handle/xzxy37.
Der volle Inhalt der QuelleAnnotation:
碩士國立中央大學
土木工程研究所
94
The value of the perishable goods will decrease by the time. In order to efficiently find the maximized profit for the manufactory, we try to integrate the production scheduling, vehicle routing problem, take into the location problem, time window constrains, and finally formulate a bi-level integer programming problem. We also propose a heuristic solution algorithm, and we fixed the location of depots at the upper-level, then to solve the lower-level. At the lower-level, we use the concept of decomposition to decompose the problem as production scheduling problem and vehicle routing problem. At the part of production schedule, we use the Nelder-Mead algorithm to solve, and use the modified insert method to construct the initial solution at the part of vehicle routing. As the result of increasing of market share ratios for frozen production by the day, therefore it is more important in the production scheduling for perishable goods and vehicle routing problem. And it’s a major factor for a business to determine the location in the beginning investment cost. The study solving the minimum long-term cost problem under the condition of short-termed optimization, therefore we construct a bi-level programming modal. For increasing the practicability of the modal, it will be an important research direction to set up friendly user interface and improve the efficient of algorithm in the future.
40
Chen, Hsiao-Chun, und 陳曉君. „A Effect of Agile Workforce Scheduling Problem in TOC Environment-A Wafer Manufacturing Process Example“. Thesis, 2003. http://ndltd.ncl.edu.tw/handle/98446485741988364252.
Der volle Inhalt der QuelleAnnotation:
碩士華梵大學
工業管理學系碩士班
91
Due to the massive implementation of automation machines, manufacturing productivity has increased drastically. Meanwhile, the change of work contents has gradually reduced labor demand. The use of “a single multi-functional operator serving several different machines” has become the norm of modern shop floor. Also the increasing acceptance of “Theory of Constraints” has a major impact to managing shop floor. With the increasing successful implementations on bottleneck oriented operations, the non-capacity constraint resources should subordinate themselves to the capacity constraint resource, many successful shop floors further demonstrate that with the use of “one multi-skilled operator serving different multi-machine” system, further job enlargement and more flexibility for utilizing human resource is achievable. The research focuses on exploring the feasibility of finding minimum number of multi-skilled labor that can satisfy the targeted throughput of a TOC oriented system with two types, an even and a lump-sum, of material releasing schemes. Based on the different skills each individual worker owns, the solution procedures use the concept of union and complement skill sets to determine either a feasible employee schedule or a needed skills list that must be acquired in order to run the system smoothly. The research also suggests the better learning orders for those less skilled workers so they can learn new skills in a manner that the system demand is always met. The simulation results indicate that without loosing any throughput, the lump-sum releasing scheme uses only 5 workers, one less than the even releasing scheme. Also the worker utilization of the lump-sum releasing scheme is also 24.37% higher than that of the other scheme.
41
Yu, Shang-Siou, und 余尚修. „Integrated Production Scheduling and Multi-Periodic Vehicle Routing Problem to Minimize Total Cost“. Thesis, 2015. http://ndltd.ncl.edu.tw/handle/28483563713945559969.
Der volle Inhalt der QuelleAnnotation:
碩士國立雲林科技大學
工業工程與管理系
104
In 21st century, the industry is confronted with a huge demand of the consumers. In the fierce competition environment, the supplier must careful considering, how to fast respond customers require. The study presents the minimized total cost of the integrating multi-periodic production and multi-periodic distribution. There is some literature to integrate the production scheduling and vehicle routing problem, but some of the study either consider the single period distribution and complex production, or the multi-periodic production and single production. In order to have a more comprehensive discussion, the study consider the above two points, unrelated parallel machine in the production environment, the multi- periodic in the distribution. The study uses a local search approach, with Particle Swarm Optimization (PSO) algorithm to solve the problem. Through experimental design to compare with differences of the tradition particle swarm optimization and the proposed heuristic particle swarm optimization, confirmed on solving this problem. And the proposed method can indeed give consideration to the quality.
42
Chin-Wei, Liu, und 劉金維. „ISSUES of THE TIME DEPENDENT SINGLE VEHICLE ROUTING AND SCHEDULING PROBLEM WITH TIME WINDOWS“. Thesis, 2000. http://ndltd.ncl.edu.tw/handle/63855989935903902122.
Der volle Inhalt der QuelleAnnotation:
博士國立中央大學
土木工程研究所
88
The thesis is focused on the static and dynamic single vehicle routing and scheduling problems for the express carriers. The static one is as the Time Dependent Traveling Salesman Problem with Time Windows（TDTSPTW）. The time dependent link cost makes a lot of difference in computational complexity and graphic property, between TDTSPTW and TSP. The other topic is the Dynamic Single Vehicle Routing and Scheduling Problem（SVRSP）. The problem not only contains all the characteristics of the TDTSPTW, but the demand pattern is not deterministic. Therefore, the routing plan must be updated when any new request is accepted. All the issues mentioned above are supplied with some numerical tests to demonstrate proposed dynamic programming based algorithms. Keyword：time dependent, time window, dynamic programming, vehicle routing
43
Tao, Yu-Hsiang, und 陶昱翔. „A Home Health Care Routing and Scheduling Problem with Synchronization, Precedence and Time Windows Constraints“. Thesis, 2018. http://ndltd.ncl.edu.tw/handle/a9r8m8.
Der volle Inhalt der QuelleAnnotation:
碩士中原大學
土木工程研究所
106
Home health care services are becoming important in hyper-aged society. Because of physiological disorder or diseases, seniors needs assistance with daily living activities in different degrees. Home care services are versatile. In this research, the Home Health Care Routing and Scheduling Problem （HHCRSP）considers services with synchronization, precedence and time windows constraints. It integrates the Nurse Rostering Problem （NRP）and the Vehicle Routing Problem with time windows（VRPTW）. The planning takes into account individual service requirements of the seniors, individual qualifications of the caregivers and possible interdependencies between different service operations. It also considers constraints related with workload and capacity among other limitations associated with seniors and caregivers. A mathematical model formulation will be proposed together with a powerful metaheuristic based on particle swarm optimization algorithms combined with local improvement procedures like insertion and swap. Because of the computational intractability, we attempt to develop the methodology to enable the continuous PSO algorithms to be efficiently applied to the HHCRSP. Several techniques will be developed for generating an initial solution which guides the search direction of the particle. Local improvements procedures will be embedded in the PSO algorithms to further improve the solution quality. The proposed methodologies will be implemented, tested, and compared with variety of instances which are generated by reasonable method.
44
Wang, Keng-Pin, und 王耿彬. „Applying genetic algorithm to the vehicle routing and scheduling problem of a frozen foods distribution center“. Thesis, 2001. http://ndltd.ncl.edu.tw/handle/45776151060831485737.
Der volle Inhalt der QuelleAnnotation:
碩士朝陽科技大學
工業工程與管理系碩士班
89
In recent years , the amount of distribution centers is growing due to the needs from industries. Vehicles and their drivers are among the most important service resources of a distribution center , and hence the utilization of these resources directly determine a distribution center’s efficiency. The purpose of this study is to investigate the routing and scheduling of vehicles of a frozen foods distribution center. This study first interviews the related industries to distinguish the key factors which affect the performance of a distribution center’s operations. According to the result of this interview , we conclude that two performance indexes could be applied to measure the scheduling operation of a distribution center: (1)the cost of transportation , and (2) the penalty cost due to violating customers’ delivery time windows . To address the above two measures, hard time windows and soft time windows are both adopted to build a mathematical model for this problem. The hard time windows are used to force a delivery arrives within a customer defined time interval, while the soft time windows are used to convert a violation of delivery time interval to a penalty cost. The resultant model has an embedded structure which enables us to decompose the original problem into a clustering master problem and many mutually independent routing sub-problems. In the solving of the master problem, a genetic algorithm is employed. As for the solving of sub-problems , a heuristic algorithm is formulated. In each iteration, the master problem is solved to form clusters of customers with respect to each vehicle, and sub-problems are solved to find optimal routing schedules for all vehicles. The performance of all the routing schedules are passed to the master problem and serve as a reference for solving the master problem again in the next interation; and the original problem is solved gradually in such a manner. To justify the performance of our model and solution procedure, three different comparisons are carried out : (1)the performance of our solution procedure and other algorithms which have been proposed in literature are compared, (2)the performances of our solution procedure on different problem sizes are compared, and (3)the effect of model decomposition is justified. The comparison results suggest that our model and solution procedure provide satisfied performance on the vehicle routing and scheduling problem.
45
Liu, Meng-Hao, und 劉孟豪. „Lagrange Relaxation Based Method for the Routing and Packet Scheduling Problem in IEEE 802.16 Mesh Networks“. Thesis, 2009. http://ndltd.ncl.edu.tw/handle/98059748638517128652.
Der volle Inhalt der QuelleAnnotation:
碩士國立雲林科技大學
電機工程系碩士班
97
The IEEE 802.16 standard, also known as the WiMAX technology, is a technology of wireless network access which can service a large area. Its transmission rate exceeds 100 Mbps, which qualifies itself to fit the category of high-speed wireless broadband network technology. Since the WiMAX technology adopts the multi-hop technique to deal with data packets among subscriber stations (SSs), only a few base stations (BSs) are required to cover a large metropolitan area. For this reason, an efficient routing and packet scheduling (RPS) algorithm is necessary to deal with SS-to-SS and SS-to-BS data transmissions. In fact, the RPS problem has recently become an important research topic in the multi-hop WiMAX. In this thesis, we study the RPS problem in the IEEE 802.16 network and propose a fast method to solve it. The multi-hop WiMAX can be subdivided into two types: WiMAX mesh networks and mobile multi-hop relay networks. Focusing on the first type, we want to design a fast centralized scheduling scheme. The objective of a scheduling scheme is to maximize the throughput of the network. In other words, we will design a fast scheduling scheme to meet the requirement of all the SSs so that all of the packets can be delivered to the BS while minimizing the number of time slots and prohibiting the interference between any two packets. The authors of literature [9] have proven that the RPS problem is NP-complete for a general network topology. It means that it must take exponential time to find the optimal solution of the RPS problem. Thus, when the number of SSs is large, it is usually impossible to find an optimum schedule within a short time. As an approach to NP-complete problems, an efficient computational methodology was proposed around 1970, namely, the Lagrange relaxation based method. The basic idea is that some constraints of a given problem can be relaxed so as to reduce the solution space, which in turn shortens the solution-searching time. In other words, this method relaxes the constraints which may otherwise make the running time of a combinatorial optimization problem become exponential. These relaxed constraints are merged into the objective function such that the original problem becomes a Lagrangian problem. In general, an optimal solution to the resultant Lagrangian problem can be obtained within a shorter period of time. In this thesis, the Lagrange relaxation based method is applied to shrink the solution space of the RPS problem for the purpose of shortening the solution-searching time. First, we theoretically transform the RPS problem into a Lagrangian RPS problem, which is then proved to be a concave function. This Lagrangian RPS problem simplifies the original RPS problem and can be used to find an optimal solution for the original RPS problem within a shorter time. In fact, to speed up the search of an optimal solution, we have cut down the solution space of the RPS problem. Our computer simulations show a decrease of the solution space by 37.73%. In other words, if the solution space must be searched by the mixed integer linear programming formulation in [9] is 100%, our method can find an optimal time slot schedule with 62.27% of its solution space. Our method is feasible. This is because different schedules of minimum time slots usually exist in the RPS problem. We eliminate 37.73% of the solution space without completely eliminating all the minimum time slot schedules. According to the computer simulations, in contrast to the mixed integer linear programming formulation in [9], our Lagrange relaxation based method can attain a minimum time slot schedule within a shorter time for the RPS problem. In terms of running time, our method can decrease its running time by 97.87%. In conclusion, our Lagrange relaxation based method is demonstrated to be valuable for its contribution of a shorter solution time.
46
Wu, De-Kuei, und 吳得魁. „Nested Variable Neighborhood Search for Solving the Integrated Problem of Parallel Machine Scheduling and Vehicle Routing“. Thesis, 2013. http://ndltd.ncl.edu.tw/handle/39448835760513227537.
Der volle Inhalt der QuelleAnnotation:
碩士國立東華大學
運籌管理研究所
102
Nowadays the manufacturing environment becomes competitive and the market demands change rapidly. Enterprises are facing with shorter product life cycles and higher levels of customer requirements and satisfaction degree. Hence, the integration of supply chain becomes important. For example, in an assembly plant, due to the factors of real-time production and zero inventory, how to effectively combine scheduling and distribution and to achieve a minimum of delay time is important. This study discusses the integrated parallel machine scheduling and vehicle routing problem with time window and considers these issues of single machine type, multi-machine, multi-order, dependent setup time, multi-vehicle, and time window to minimize the total weighted tardiness. In addition, this study develops a nested variable neighborhood search method to solve this integrated problem. Through small-scale problems, the proposed approach is compared with the optimal solution obtained from the branch and bound method. It can also be found that the proposed nested variable neighborhood search can obtain the feasible solution quickly and effectively from the outcomes of large-scale problems.
47
Hu, Chuan-Fu, und 胡全福. „An Efficient and Interference-Aware Centralized Routing Tree Algorithm for the Packet Scheduling Problem in IEEE 802.16 Mesh Networks“. Thesis, 2009. http://ndltd.ncl.edu.tw/handle/54799607847230055768.
Der volle Inhalt der QuelleAnnotation:
碩士國立雲林科技大學
電機工程系碩士班
97
Recent years have seen an ever-increasing demand for wireless and mobile communications. However, the development of current wireless and mobile communications is overshadowed by high prices, limited access, and low transmission rate. In response to the drawbacks, the wireless metropolitan area networks standard—IEEE 802.16 (or WiMAX) standard—is proposed. IEEE 802.16 standard aims to provide high speed data transmission rate and easy deployment in remote areas. In addition, it can be used as a last mile broadband wireless access. IEEE 802.16 standard supports two configuration modes: Point to Multipoint (PMP) and Mesh. This thesis studies the IEEE 802.16 Mesh mode. In addition to establishing a direct communication link between a subscriber station and the base station, the IEEE 802.16 Mesh mode allows the subscriber station to use the hop-by-hop method to transmit data packets to the base station. Therefore, as far as the IEEE 802.16 Mesh mode is concerned, the routing and packet scheduling problem becomes one of the most important research issues. In this thesis, we design an efficient and interference-aware centralized routing tree algorithm which takes the number of interferences associated with a subscriber station into consideration in an IEEE 802.16 Mesh network. Our routing tree algorithm enables more subscriber stations to conduct simultaneous transmissions, which efficiently shortens the scheduling length, and increases both the channel utilization ratio and the system throughput. In other words, our routing tree algorithm is capable of enhancing the overall performance of the network. Simulation results show that our routing tree algorithm outperforms the IEEE 802.16 standard by achieving a 10 to 12 percent of decrease in the scheduling length, and a 10 to 12 percent of increase in both the channel utilization ratio and the system throughput. Compared with the two algorithms proposed by Hemyari et al., our routing tree algorithm achieves a 3 to 6 percent of decrease in the scheduling length, and a 3 to 6 percent of increase in both the channel utilization ratio and the system throughput.
48
Moolman, A. J. (Alwyn Jakobus). „Design and implementation of an integrated algorithm for the vehicle routing problem with multiple constraints“. Diss., 2004. http://hdl.handle.net/2263/25036.
Der volle Inhalt der Quelle
49
Vidal, Thibaut. „Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires“. Thèse, 2013. http://hdl.handle.net/1866/9699.
Der volle Inhalt der QuelleAnnotation:
Le problème de tournées de véhicules (VRP) implique de planifier les itinéraires d'une flotte de véhicules afin de desservir un ensemble de clients à moindre coût. Ce problème d'optimisation combinatoire NP-difficile apparait dans de nombreux domaines d'application, notamment en logistique, télécommunications, robotique ou gestion de crise dans des contextes militaires et humanitaires. Ces applications amènent différents contraintes, objectifs et décisions supplémentaires ; des "attributs" qui viennent compléter les formulations classiques du problème. Les nombreux VRP Multi-Attributs (MAVRP) qui s'ensuivent sont le support d'une littérature considérable, mais qui manque de méthodes généralistes capables de traiter efficacement un éventail significatif de variantes. Par ailleurs, la résolution de problèmes "riches", combinant de nombreux attributs, pose d'importantes difficultés méthodologiques.
Cette thèse contribue à relever ces défis par le biais d'analyses structurelles des problèmes, de développements de stratégies métaheuristiques, et de méthodes unifiées. Nous présentons tout d'abord une étude transversale des concepts à succès de 64 méta-heuristiques pour 15 MAVRP afin d'en cerner les "stratégies gagnantes". Puis, nous analysons les problèmes et algorithmes d'ajustement d'horaires en présence d'une séquence de tâches fixée, appelés problèmes de "timing". Ces méthodes, développées indépendamment dans différents domaines de recherche liés au transport, ordonnancement, allocation de ressource et même régression isotonique, sont unifiés dans une revue multidisciplinaire.
Un algorithme génétique hybride efficace est ensuite proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration agressive des métaheuristiques à voisinage, et une évaluation bi-critère des solutions considérant coût et contribution à la diversité de la population. Les meilleures solutions connues de la littérature sont retrouvées ou améliorées pour le VRP classique ainsi que des variantes avec multiples dépôts et périodes. La méthode est étendue aux VRP avec contraintes de fenêtres de temps, durée de route, et horaires de conducteurs. Ces applications mettent en jeu de nouvelles méthodes d'évaluation efficaces de contraintes temporelles relaxées, des phases de décomposition, et des recherches arborescentes pour l'insertion des pauses des conducteurs. Un algorithme de gestion implicite du placement des dépôts au cours de recherches locales, par programmation dynamique, est aussi proposé. Des études expérimentales approfondies démontrent la contribution notable des nouvelles stratégies au sein de plusieurs cadres méta-heuristiques.
Afin de traiter la variété des attributs, un cadre de résolution heuristique modulaire est présenté ainsi qu'un algorithme génétique hybride unifié (UHGS). Les attributs sont gérés par des composants élémentaires adaptatifs. Des expérimentations sur 26 variantes du VRP et 39 groupes d'instances démontrent la performance remarquable de UHGS qui, avec une unique implémentation et paramétrage, égalise ou surpasse les nombreux algorithmes dédiés, issus de plus de 180 articles, révélant ainsi que la généralité ne s'obtient pas forcément aux dépends de l'efficacité pour cette classe de problèmes. Enfin, pour traiter les problèmes riches, UHGS est étendu au sein d'un cadre de résolution parallèle coopératif à base de décomposition, d'intégration de solutions partielles, et de recherche guidée.
L'ensemble de ces travaux permet de jeter un nouveau regard sur les MAVRP et les problèmes de timing, leur résolution par des méthodes méta-heuristiques, ainsi que les méthodes généralistes pour l'optimisation combinatoire.The Vehicle Routing Problem (VRP) involves designing least cost delivery routes to service a geographically-dispersed set of customers while taking into account vehicle-capacity constraints. This NP-hard combinatorial optimization problem is linked with multiple applications in logistics, telecommunications, robotics, crisis management in military and humanitarian frameworks, among others. Practical routing applications are usually quite distinct from the academic cases, encompassing additional sets of specific constraints, objectives and decisions which breed further new problem variants. The resulting "Multi-Attribute" Vehicle Routing Problems (MAVRP) are the support of a vast literature which, however, lacks unified methods capable of addressing multiple MAVRP. In addition, some "rich" VRPs, i.e. those that involve several attributes, may be difficult to address because of the wide array of combined and possibly antagonistic decisions they require. This thesis contributes to address these challenges by means of problem structure analysis, new metaheuristics and unified method developments. The "winning strategies" of 64 state-of-the-art algorithms for 15 different MAVRP are scrutinized in a unifying review. Another analysis is targeted on "timing" problems and algorithms for adjusting the execution dates of a given sequence of tasks. Such methods, independently studied in different research domains related to routing, scheduling, resource allocation, and even isotonic regression are here surveyed in a multidisciplinary review. A Hybrid Genetic Search with Advanced Diversity Control (HGSADC) is then introduced, which combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and a bi-criteria evaluation of solutions based on cost and diversity measures. Results of remarkable quality are achieved on classic benchmark instances of the capacitated VRP, the multi-depot VRP, and the periodic VRP. Further extensions of the method to VRP variants with constraints on time windows, limited route duration, and truck drivers' statutory pauses are also proposed. New route and neighborhood evaluation procedures are introduced to manage penalized infeasible solutions w.r.t. to time-window and duration constraints. Tree-search procedures are used for drivers' rest scheduling, as well as advanced search limitation strategies, memories and decomposition phases. A dynamic programming-based neighborhood search is introduced to optimally select the depot, vehicle type, and first customer visited in the route during local searches. The notable contribution of these new methodological elements is assessed within two different metaheuristic frameworks. To further advance general-purpose MAVRP methods, we introduce a new component-based heuristic resolution framework and a Unified Hybrid Genetic Search (UHGS), which relies on modular self-adaptive components for addressing problem specifics. Computational experiments demonstrate the groundbreaking performance of UHGS. With a single implementation, unique parameter setting and termination criterion, this algorithm matches or outperforms all current problem-tailored methods from more than 180 articles, on 26 vehicle routing variants and 39 benchmark sets. To address rich problems, UHGS was included in a new parallel cooperative solution framework called "Integrative Cooperative Search (ICS)", based on problem decompositions, partial solutions integration, and global search guidance. This compendium of results provides a novel view on a wide range of MAVRP and timing problems, on efficient heuristic searches, and on general-purpose solution methods for combinatorial optimization problems.
Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes
50
Mathlouthi, Ines. „Méthodes de résolution exactes et heuristiques pour un problème de tournées de techniciens“. Thèse, 2017. http://hdl.handle.net/1866/20484.
Der volle Inhalt der Quelle