Pickup and Delivery Problems (PDPs) constitute a class of Vehicle Routing Problems (VRPs) consisting of finding the optimal routes for a fleet of vehicles to deliver requests from a set of origin locations to a corresponding set of destinations. PDPs are NP-hard and have a wide variety of variants and potential constraints. This thesis evaluates methods for solving a dynamic single- vehicle PDP restricted by multiple time-related constraints. The problem is dynamic in the sense that new requests arrive as time is simulated and inserted into the vehicle’s pickup and delivery plan as it is being executed. The time- related constraints include limited time windows during which the requests may be picked up or delivered, as well as maximum ride times that items may spend in the vehicle before being delivered. To solve the problem, we adapt insertion heuristics based on Large Neighborhood Search (LNS) and Heuristic Destroy and Repair (HDR) to the problem and evaluate them in a comparative study. Solution methods for the PDP are also applied on the problem of dynamically assigning incoming orders to vehicles in a delivery service with a short planning horizon. A PDP-based order assignment strategy is compared with assignment strategies based on proximity and workload. Due to the short planning horizon of the target application, the study is focused on finding well-performing methods for quickly solving small PDPs containing 10-15 requests. Our results indicate that LNS outperforms HDR for small problem instances. However, the quick convergence of HDR allows it to outperform LNS for larger problem instances. We also show that applying a PDP- based assignment strategy in the order assignment problem allows the service to accommodate more requests than the alternative assignment strategies while simultaneously providing a significant reduction in operational costs. Future work may improve the order assignment strategy by incorporating more anticipatory functionality and streamlining the PDP methods with more efficient tests for the feasibility of solutions. / Pickup and Delivery Problems (PDP:er) utgör en grupp av Vehicle Routing Problems (VRP:er) som består av att hitta de optimala rutterna för en fordonsflotta för att leverera beställningar från en uppsättning av upplockningsplatser till motsvarande uppsättning av avlämningsplatser. PDP:er är NP-svåra och har en stor mängd olika varianter och potentiella begränsningar. Denna avhandling utvärderar metoder för att lösa ett dynamiskt enkel-fordon PDP med flera tidsrelaterade begränsningar. Problemet är dynamiskt i den mening att nya beställnigar anländer i samband med att tiden simuleras och sätts in i fordonets leveransplan samtidigt som den utförs. De tidsrelaterade begränsningarna innefattar begränsade tidsfönstren under vilka beställningar kan plockas upp eller lämnas av, samt maximala tider som hämtade föremål får tillbringa i fordonet innan de lämnas av. För att lösa problemet anpassar vi insättningsheuristiker baserade på Large Neighborhood Search (LNS) och Heuristic Destroy and Repair (HDR) till problemet och utvärderar dem i en jämförande studie. Lösningsmetoder för PDP tillämpas också på problemet att dynamiskt tilldela inkommande beställningar till fordon i en leveransservice med en kort planeringshorisont. En PDP-baserad tilldelningsstrategi jämförs med strategier baserade på närhet och arbetsbelastning. På grund av målapplikationens korta planeringshorisont så fokuserar studien på att hitta väl presterande metoder för att snabbt lösa små PDP:er som innehåller 10-15 förfrågningar. Våra resultat indikerar att LNS överträffar HDR för små probleminstanser. Däremot leder den snabba konvergensen av HDR till att den överträffar LNS för större probleminstanser. Vi visar också att tillämpningen av en PDP-baserad tilldelningsstrategi i tilldelningsproblemet gör att tjänsten kan tillgodose fler beställningar än de alternativa tilldelningsstrategierna, samtidigt som det ger en betydlig minskning av driftskostnaderna. Framtida arbete kan förbättra tilldelningsstrategin genom att integrera mer förutseende funktionalitet och effektivisera PDP-metoderna med ett mer effektivt test av genomförbarhet för lösningar.

No description available.

No description available.

No description available.

No description available.

[pt] A presente pesquisa buscou investigar como ocorre a mediação na tríade aluno-tutor-orientador em busca da aquisição da autonomia e da autoria discente durante a elaboração do trabalho de conclusão de curso (TCC) na modalidade da Educação a Distância (EaD). Partiu-se do pressuposto de que a apropriação dos conceitos científicos apresentados em cursos de especialização pela Universidade Aberta do Brasil (UAB) não ocorre no isolamento, mas por meio da intervenção intencional de professores-tutores e professores-orientadores. Esses professores contribuiriam para construção do pensamento teórico, elemento fundante da autonomia acadêmica e da autoria para escrita do TCC. Para fundamentar o estudo, foi adotada a abordagem histórico-cultural e a metodologia convergiu com esse referencial. Foram aplicados: 235 questionários on-line aos ex-alunos que concluíram cursos de especialização pela UAB, em diversos estados e instituições; quatro grupos focais on-line (GFO) para professores-tutores e professores-orientadores, alcançando 24 participantes; e sete entrevistas com os professores que não puderam participar do GFO. Os dados coletados foram analisados a partir de três eixos temáticos: autonomia, autoria e mediação. Os resultados evidenciaram que há pelo menos dois fatores que a tríade aponta como essenciais para a realização do TCC: o tempo disponível e o atendimento às normas acadêmicas e éticas durante a autoria. Enquanto para os ex-alunos o fator tempo estava associado à disponibilidade para dedicar-se aos estudos, para os professores, relacionava-se ao prazo insuficiente estabelecido pela instituição para realizar a mediação necessária para auxiliar os alunos na escrita do TCC. Foi possível concluir que os participantes da tríade percebem a autonomia acadêmica como um pré-requisito para iniciar a elaboração do TCC, e não como uma aquisição que ocorre durante o processo de autoria. Os participantes apontaram para a necessidade de acompanhamento mais próximo do aluno, com clareza e agilidade nos feedbacks, ancorados na afetividade. As condições concretas e objetivas que atravessam a realização do TCC não permitiram aos participantes, priorizarem as intervenções docentes para o desenvolvimento do aluno e do pensamento teórico. Apesar disso, ao buscarem a superação da alienação (LEONTIEV, 2004) dessas condições, conseguiram concluir o trabalho, encontrando formas de delegar a um segundo plano todos os desafios que emergiram durante a escrita autoral do trabalho científico dos alunos. / [en] The present research investigates how mediation occurs in the triad student- tutor-advisor in distance education for building autonomy and student authorship during the elaboration of the Final Course Assignment (FCA). We assumed that the appropriation of scientific concepts in specialization courses by the Open University System of Brazil (UAB) does not occur in isolation but through the intentional intervention of tutors and advisors. These teachers would contribute to the building of theoretical thinking, a founding element of academic autonomy and authorship for writing the FCA. We based the study on the historical-cultural approach, and the methodology converged with this referential. We applied: 235 online questionnaires to alumni who completed specialization courses at UAB, in several states and institutions; four online focus groups (OFG) for tutors and advisors, reaching 24 participants; and seven interviews with teachers who were not able to participate in the OFG. We analyzed the collected data using three thematic axes: autonomy, authorship, and mediation. The results showed at least two factors that the triad points out as essential for writing the FCA: the available time and the observation of academic and ethical norms. While for the former students the time factor was associated with the availability to dedicate themselves to the studies, for the teachers, it was related to the insufficient given period to carry out the necessary mediation to assist students in their FCA. We conclude that the participants sensed academic autonomy as a prerequisite for initiating FCA rather than as a building process that occurs along with the writing. Participants pointed to the need for closer follow-up with the students, including clarity and agility in feedback, while sustaining affectivity. The concrete and objective conditions that go through the development of the FCA did not allow participants to prioritize teaching interventions for students improvement and development of theoretical thinking. Nevertheless, in seeking to overcome the alienation (LEONTIEV, 2004) of these conditions, they were able to conclude their work, by finding a way to alleviate the difficulties emerged during the authorial writing of the scientific works.

For unmanned vehicles, autonomy means that the vehicle’s route can be planned and executed according to some pre-defined rules in the absence of human intervention. Autonomous vehicles (AVs) have become a common type of vehicle for various kinds of transport, for example autonomous forklifts within a warehouse environment. Volvo Autonomous Solution (VAS) works with autonomous vehicles in different areas. To better understand how different methods can be used for planning of autonomous vehicles, VAS initiated this project. To increase the efficiency of AVs, several problems can be examined. One such problem is the allocation problem, also called Multi-Robot Task Allocation, which aims to find out which vehicle should execute which task to achieve a global goal cooperatively. The AVs used by VAS handle Planning Missions (PMs). A PM is, for example, to move goods from a loading point to an unloading point. So, the problem examined in this study is how to assign PMs to vehicles in the most efficient way. The thesis also includes a collection of publications on the area. The problem is solved by using three methods: Mixed Integer Linear Programming (MILP), a Genetic Algorithm that was originally proposed for task assignment in a warehouse environment (GA – Warehouse), and a Genetic Algorithm that was initially proposed for train scheduling (GA – Train). With the MILP method, the problem has been formulated mathematically and the method guarantees an optimal solution. However, the major drawback of this approach is the large computational time required to retrieve a solution. The GA – Warehouse method has a quite simple allocation process but a more complicated path planning part and is, in its entirety, not as flexible as the other methods. The GA – Train method has a lower computational time and can consider many different aspects. All three methods generate similar solutions for the limited set of simple scenarios in this study, but an optimal solution can only be guaranteed by the MILP method. Regardless of which method is used, there is always a trade-off: a guarantee of the optimal solution at the expense of high computational time or a result where no optimal solution can be guaranteed but can be generated quickly. Which method to use depends on the context, what resources are available, and what requirements are placed on the solution. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

<p>This work investigates the assignment of unknown sequences to their species of origin. In particular, I examine four questions: Is existing (GenBank) data reliable for accurate species identification? Does a segregating sites algorithm make accurate species identifications and how does it compare to another Bayesian method? Does broad sampling of reference species improve the information content of reference data? And does an extended model (of the theory of segregating sites) describe the genetic variation in a set of sequences (of a species or population) better? Though we did not find unusually similar between-species sequences in GenBank, there was evidence of unusually divergent within-species sequences, suggesting that caution and a firm understanding of GenBank species should be exercised before utilizing GenBank data. To address challenging identifications resulting from an overlap between within- and between species variation, we introduced a Bayesian treeless statistical assignment method that makes use of segregating sites. Assignments with simulated and <em>Drosophila</em> (fruit fly) sequences show that this method can provide fast, high probability assignments for recently diverged species. To address reference sequences with low information content, the addition of even one broadly sampled reference sequence can increase the number of correct assignments. Finally, an extended theory of segregating sites generates more realistic probability estimates of the genetic variability of a set of sequences. Species are dynamic entities and this work will highlight ideas and methods to address dynamic genetic patterns in species.</p> / Doctor of Philosophy (PhD)

<p>This thesis contains two parts. In the first part, which contains Chapter 2 and Chapter 3, we consider scheduling problems with learning effect and time-dependent processing time on a single machine. In Chapter 2, we investigate the earliness-tardiness objective, as well as the objective without due date assignment consideration. By reducing them to a special linear assignment problem, we solve them in near-linear time. As a consequence, we improve the time complexity for some previous algorithms for scheduling problems with learning effect and/or time-dependent processing time. In Chapter 3, we investigate the total number of tardy jobs objective. By reducing them to a linear assignment problem, we solve them in polynomial time. For some important special cases, where there is only learning effect OR time-dependent processing time, we reduce the time complexity to quadratic time. In the second part, which contains Chapter 4 and Chapter 5, we investigate the bicriteria scheduling problems in a supply chain. We separate the objectives in two parts, where the delivery cost is one of them. We present efficient algorithms to identify all the Pareto-optimal solutions for various scenarios. In Chapter 4, we study the cases without due date assignment; while in Chapter 5 we study the cases with due date assignment consideration.</p>

Stochastic programming is an optimization technique that incorporates random variables as parameters. Because it better reflects the uncertain real world than its traditional deterministic counterpart, stochastic programming has drawn increasingly more attention among decision-makers, and its applications span many fields including financial engineering, health care, communication systems, and supply chain management. On the flip side, stochastic programs are usually very difficult to solve, which is further compounded by the fact that in many of the aforementioned applications, we also have discrete decisions, thereby rendering these problems even more challenging. In this dissertation, we study the class of two-stage stochastic mixed-integer programs (SMIP), which, as its name suggests, lies at the confluence of two formidable classes of problems. We design a novel algorithm for this class of problems, and also explore specialized approaches for two related real-world applications. Although a number of algorithms have been developed to solve two-stage SMIPs, most of them deal with problems containing purely integer or continuous variables in either or both of the two stages, and frequently require the technology and/or recourse matrices to be deterministic. As a ground-breaking effort, in this work, we address the challenging class of two-stage SMIPs that involve 0-1 mixed-integer variables in both stages. The only earlier work on solving such problems (Car&#248;e and Schultz (1999)) requires the optimization of several non-smooth Lagrangian dual problems using subgradient methods in the bounding process, which turns out to be computationally very expensive. We begin with proposing a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having 0-1 mixed-integer variables in both stages. Since the second-stage problems contain binary variables, their value functions are in general nonconvex and discontinuous; hence, the classical Benders' decomposition approach (or the L-shaped method) for solving two-stage stochastic programs, which requires convex subproblem value functions, cannot be directly applied. This motivates us to relax the second-stage problems and accompany this relaxation with a convexification process. To make this process computationally efficient, we propose to construct a certain partial convex hull representation of the two-stage solution space, using the relaxed second-stage constraints and the restrictions confining the first-stage variables to lie within some hyperrectangle. This partial convex hull is sequentially generated using a convexification scheme, such as the Reformulation-Linearization Technique (RLT), which yields valid inequalities that are functions of the first-stage variables and, of noteworthy importance, are reusable in the subsequent subproblems by updating the values of the first-stage variables. Meanwhile, since the first stage contains continuous variables, whenever we tentatively fix these variables at some given feasible values, the resulting constraints may not be facial with respect to the associated bounding constraints that are used to construct the partial convex hull. As a result, the constructed Benders' subproblems define lower bounds for the second-stage value functions, and likewise, the resulting Benders' master problem provides a lower bound for the original stochastic program defined over the same hyperrectangle. Another difficulty resulting from continuous first-stage variables is that when the given first-stage solution is not extremal with respect to its bounds, the second-stage solution obtained for a Benders' subproblem defined with respect to a partial convex hull representation in the two-stage space may not satisfy the model's binary restrictions. We thus need to be able to detect whether or not a Benders' subproblem is solved by a given fractional second-stage solution. We design a novel procedure to check this situation in the overall algorithmic scheme. A key property established, which ensures global convergence, is that these lower bounds become exact if the given first-stage solution is a vertex of the defining hyperrectangle, or if the second-stage solution satisfies the binary restrictions. Based on these algorithmic constructs, we design a branch-and-bound procedure where the branching process performs a hyperrectangular partitioning of the projected space of the first-stage variables, and lower bounds for the nodal problems are computed by applying the proposed modified Benders' decomposition method. We prove that, when using the least-lower-bound node-selection rule, this algorithm converges to a global optimal solution. We also show that the derived RLT cuts are not only reusable in subsequent Benders iterations at the same node, but are also inheritable by the subproblems of the children nodes. Likewise, the Benders' cuts derived for a given sub-hyperrectangle can also be inherited by the lower bounding master programs solved for its children nodes. Using these cut inheritance properties results in significant savings in the overall computational effort. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach. The sizes of the deterministic equivalent of our test problems range from having 386 continuous variables, 386 binary variables, and 386 constraints, up to 1795 continuous variables, 1539 binary variables, and 1028 constraints. The results reveal an average savings in computational effort by a factor of 9.5 in comparison with using a commercial mixed-integer programming package (CPLEX 8.1) on a deterministic equivalent formulation. We then explore an important application of SMIP to enhance the traditional airline fleet assignment models (FAM). Given a flight schedule network, the fleet assignment problem solved by airline companies is concerned with assigning aircraft to flight legs in order to maximize profit with respect to captured path- or itinerary-based demand. Because certain related crew scheduling regulations require early information regarding the type of aircraft serving each flight leg, the current practice adopted by airlines is to solve the fleet assignment problem using estimated demand data 10-12 weeks in advance of departure. Given the level of uncertainty, deterministic models at this early stage are inadequate to obtain a good match of aircraft capacity with passenger demands, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. From this viewpoint, the initial decision should embrace various market scenarios so that it incorporates a sufficient look-ahead feature and provides sufficient flexibility for the subsequent re-fleeting processes to accommodate the inevitable demand fluctuations. With this motivation, we propose a two-stage stochastic programming approach in which the first stage is concerned with the initial fleet assignment decisions and, unlike the traditional deterministic methodology, focuses on making only a family-level assignment to each flight leg. The second stage subsequently performs the detailed assignments of fleet types within the allotted family to each leg under each of the multiple potential scenarios that address corresponding path- or itinerary-based demands. In this fashion, the initial decision of what aircraft family should serve each flight leg accomplishes the purpose of facilitating the necessary crew scheduling decisions, while judiciously examining the outcome of future re-fleeting actions based on different possible demand scenarios. Hence, when the actual re-fleeting process is enacted several weeks later, this anticipatory initial family-level assignment will hopefully provide an improved overall fleet type re-allocation that better matches demand. This two-stage stochastic model is complemented with a secondary model that performs adjustments within each family, if necessary, to provide a consistent fleet type-assignment information for accompanying decision processes, such as yield management. We also propose several enhanced fleet assignment models, including a robust optimization model that controls decision variation among scenarios and a stochastic programming model that considers the recapture effect of spilled demand. In addition to the above modeling concepts and framework, we also contribute in developing effective solution approaches for the proposed model, which is a large-scale two-stage stochastic 0-1 mixed-integer program. Because the most pertinent information needed from the initial fleet assignment is at the family level, and the type-level assignment is subject to change at the re-fleeting stage according to future demand realizations, our solution approach focuses on assigning aircraft families to the different legs in the flight network at the first stage, while finding relaxed second-stage solutions under different demand scenarios. Based on a polyhedral study of a subsystem extracted from the original model, we derive certain higher-dimensional convex hull as well as partial convex hull representations for this subsystem. Accordingly, we propose two variants for the primary model, both of which relax the binary restrictions on the second-stage variables, but where the second variant then also accommodates the partial convex hull representations, yielding a tighter, albeit larger, relaxation. For each variant, we design a suitable solution approach predicated on Benders' decomposition methodology. Using certain realistic large-scale flight network test problems having 900 flight legs and 1,814 paths, as obtained from United Airlines, the proposed stochastic modeling approach was demonstrated to increase daily expected profits by about 3% (which translates to about $160 million per year) in comparison with the traditional deterministic model in present usage, which considers only the expected demand. Only 1.6% of the second-stage binary variables turn out to be fractional in the first variant, and this number is further reduced to 1.2% by using the tighter variant. Furthermore, when attempting to solve the deterministic equivalent formulation for these two variants using a commercial mixed-integer programming package (CPLEX 8.1), both the corresponding runs were terminated after reaching a 25-hour cpu time limit. At termination, the software was still processing the initial LP relaxation at the root node for each of these runs, and no feasible basis was found. Using the proposed algorithms, on the other hand, the solution times were significantly reduced to 5 and 19 hours for the two variants, respectively. Considering that the fleet assignment models are solved around three months in advance of departure, this solution time is well acceptable at this early planning stage, and the improved quality in the solution produced by considering the stochasticity in the system is indeed highly desirable. Finally, we address another practical workforce planning problem encountered by a global financial firm that seeks to manage multi-category workforce for functional areas located at different service centers, each having office-space and recruitment-capacity constraints. The workforce demand fluctuates over time due to market uncertainty and dynamic project requirements. To hedge against the demand fluctuations and the inherent uncertainty, we propose a two-stage stochastic programming model where the first stage makes personnel recruiting and allocation decisions, while the second stage, based on the given personnel decision and realized workforce demand, decides on the project implementation assignment. The second stage of the proposed model contains binary variables that are used to compute and also limit the number of changes to the original plan. Since these variables are concerned with only one quality aspect of the resulting workforce plan and do not affect feasibility issues, we replace these binary variables with certain conservative policies regarding workforce assignment change restrictions in order to obtain more manageable subproblems that contain purely continuous variables. Numerical experiments reveal that the stochastic programming approach results in significantly fewer alterations to the original workforce plan. When using a commercial linear programming package CPLEX 9.0 to solve the deterministic equivalent form directly, except for a few small-sized problems, this software failed to produce solutions due to memory limitations, while the proposed Benders' decomposition-based solution approach consistently solved all the practical-sized test problems with reasonable effort. To summarize, this dissertation provides a significant advancement in the algorithmic development for solving two-stage stochastic mixed-integer programs having 0-1 mixed-integer variables in both stages, as well as in its application to two important contemporary real-world applications. The framework for the proposed solution approaches is to formulate tighter relaxations via partial convex hull representations and to exploit the resulting structure using suitable decomposition methods. As decision robustness is becoming increasingly relevant from an economic viewpoint, and as computer technological advances provide decision-makers the ability to explore a wide variety of scenarios, we hope that the proposed algorithms will have a notable positive impact on solving stochastic mixed-integer programs. In particular, the proposed stochastic programming airline fleet assignment and the workforce planning approaches studied herein are well-poised to enhance the profitability and robustness of decisions made in the related industries, and we hope that similar improvements are adapted by more industries where decisions need to be made in the light of data that is shrouded by uncertainty. / Ph. D.