查看更多>>摘要：Port terminals play a critical role in the context of world trade since they are the main nodes responsi-ble for connecting sea and land transportation. There are several optimization problems arising in port terminals, and those involving berth allocation are among the most important ones. They constitute the first level of terminal planning operations. As a consequence, the corresponding decisions impact all the subsequent operations in the port terminals. Berth allocation decisions are often integrated with quay crane assignment and/or scheduling decisions. However, the quality of these decisions is greatly affected by unpredictable events that may occur frequently. Since 2006, different approaches have been proposed for solving general berth allocation problems under uncertainty. This paper provides an exhaustive sur-vey of the works published in the literature addressing berth allocation and berth allocation and quay cranes assignment/scheduling problems under uncertainty. The publications are classified into three main classes of approaches: proactive, reactive, and proactive/reactive. An overview of the main methodologies proposed, including stochastic programming, robust optimization, fuzzy programming, and deterministic approaches, is provided. The common sources of uncertainty are identified, and the representation of the uncertain parameters is highlighted. The papers are also classified according to the main objectives to be optimized and the solution methods proposed. We identify several research trends, limitations in the current literature and future research directions.(c) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：Railway timetable planning is one of the key factors in the successful operation of a railway network. The timetable must satisfy all operational restrictions at a microscopic representation of the railway network, while maximizing transportation capacity for passengers and freight. The microscopic planning of a railway timetable is an NP-Hard problem, difficult to solve for large-scale railway networks, such as those of entire countries. In this work, we propose a logic Benders decomposition approach to solve the problem of microscopic railway timetable planning. Our decomposition exploits the typical structure of a railway with dense networks around major hubs and sparse connections in-between hubs. A logic Benders cut is designed, which we are able to compute effectively for all decomposed problems within our considered structure, using a SAT based algorithm we developed. Moreover, an aggregation scheme for Benders cuts is proposed to speed up the iterative process. Experiments on real-world cases of the Swiss Federal Railways show a clear improvement in scalability compared to a variety of benchmarks including centralized approaches.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ )
查看更多>>摘要：We consider an inverse counterpart of the interval scheduling problem. In the problem, we are given a set of machines and the objective is to reduce the non-preemptive job intervals with a least cost so that all jobs with positive processing times may be scheduled on the machines. The paper focuses on the single machine case. We establish the strong NP-hardness of the problem and show however it admits a polynomial time approximation scheme.(c) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：The multi-profit orienteering problem (MPOP), a variant of the orienteering problem, was introduced in 2020. In MPOP, each vertex has multiple profits, and a profit is determined by the time of visit. Therefore, the vertices to visit as well as the visit sequence and visit times must be optimally selected. The purpose of MPOP is to maximize the total profits collected from the vertices while satisfying the travel time limit constraint. To date, no exact algorithm has been developed for MPOP. This paper proposes a dynamic programming (DP)-based exact algorithm for MPOP for the first time. The proposed algorithm combines DP, ng-route relaxed DP, incumbent solution generation algorithms, and bounding rules. The proposed algorithm can obtain the optimal solutions for 33 previously unsolved benchmark instances and update the best solutions in 23 benchmark instances for MPOP.(c) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：Recoverable robust optimization is a multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We analyze this approach for a class of selection problems. The aim is to choose a fixed number of items from several disjoint sets, such that the worst case costs after taking a recovery action are as small as possible. The uncertainty is modeled as a discrete budgeted set, where the adversary can increase the costs of a fixed number of items. While special cases of this problem have been studied before, its complexity has remained open. In this work we make several contributions towards closing this gap. We show that the problem is NP-hard and identify a special case that remains solvable in polynomial time. We provide a compact mixed-integer programming formulation and two additional extended formulations. Finally, computational results are provided that compare the efficiency of different exact solution approaches.(c) 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )
查看更多>>摘要：This paper addresses a practical production problem in an aviation manufacturing factory that focuses on the production of composite aeronautic products, where packing and assembling are two major operations conducted in the production process. We extract a novel integer programming model that integrates bin packing with the multi-level lot-sizing problem, which is characterized by re-configurable bins and configuration-dependent processing time. To obtain tighter lower bounds, we decompose the original model into a master problem and several sub-problems based on the Dantzig-Wolfe framework. To accelerate the column generation process, we develop a bi-level dynamic programming algorithm to solve the sub-problems exactly. A hybrid algorithm that combines the column generation and the fix and-optimize heuristic is proposed to generate high-quality upper bounds. We first evaluate the quality of the lower bounds obtained from the linearly relaxed restricted master problem and then demonstrate the competitiveness of the proposed heuristic algorithm in terms of the solution quality and computational efficiency by comparing it with CPLEX, a commercial solver. In addition, we conduct sensitivity analysis of the bi-level dynamic programming to investigate the impact of the processing time required by the configuration-based bins. Moreover, a case study was conducted, which demonstrated the effect on cost reduction by shortening the length of unit time period in the planning horizon.(c) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：The two-machine flow shop problem with buffers where one of the machines has constant processing times is studied. It is investigated if optimal permutation schedules exist, i.e., schedules which minimize the makespan within the set of all schedules and where the job sequence on both machines is the same. Two standard buffer models (an intermediate buffer that a job occupies between its processing on the two machines and a spanning buffer which is occupied by a job over all of its processing steps) are considered for two types of buffer usage: i) all jobs occupy the same buffer amount and ii) for each job the occupied buffer amount equals its processing time on the machine with non-constant times. For (i) and both buffer models, it is shown that the set of optimal schedules always contains at least one permutation schedule. For (ii) the existence of optimal permutation schedules is only guaranteed for instances with n jobs for all n < 6 (spanning buffer) and for all n < 3 (intermediate buffer). For each n > 6 (spanning buffer) and each n > 3 (intermediate buffer) exists an instance which does not have an optimal permutation schedule. For (ii) and both buffer models, an upper bound and a lower bound for ratio between the makespan of a best permutation schedule and the makespan of an optimal schedule is given. It is also shown for (ii) and both buffer models that in general it is NP -hard to decide if an optimal permutation schedule exists.
查看更多>>摘要：We study the scheduling of jobs on a single parallel-batching machine with non-identical job sizes and incompatible job families. Jobs from the same family have the same processing time and can be loaded into a batch, as long as the batch size respects the machine capacity. The objective is to minimize the total weighted completion time; this common scheduling objective is equivalent with the minimization of in-process inventory when all jobs have the same release date. Our problem combines two classic combinatorial problems, namely bin packing and single machine scheduling. We develop three new mixed integer linear-programming formulations, namely an assignment-based formulation, a time-indexed formulation (TIF), and a set-partitioning formulation (SPF). We also propose a column generation (CG) algorithm for the SPF, a branch-and-price (B&P) algorithm and a CG-based heuristic. A heuristic framework based on proximity search is also developed using the TIF. We examine how to reduce the size (number of variables) of the formulations in a preprocessing step. The SPF and B&P can solve instances with non unit and unit job durations to optimality with up to 80 and 150 jobs within reasonable runtime limits, respectively. The proposed heuristics perform better than the methods available in the literature for the same problem.(c) 2022 Elsevier B.V. All rights reserved.
查看更多>>摘要：The success of e-commerce business offering same-day delivery depends on customer satisfaction. To speed up deliveries and lower costs, some companies have been using private individuals as non dedicated drivers to perform pickup and delivery tasks for online customers. Such delivery systems are known as crowd-shipping. Customers have come to expect an accurate estimate for the delivery times of their online orders. The coordination of online deliveries with private individuals is done by a crowd shipping platform. In this paper, we focus on the estimation of pickup and delivery times. This is a challenging job because not only are the requests unknown and submitted dynamically, but so is the pool of drivers, i.e. delivery capacity. We model the problem as a Markov decision process and integrate it into a simulation study. To improve the estimates that can be done by a naive policy, we propose two policies that use lookahead: one with a fixed lookahead horizon and one with a dynamic. Our numerical experiments demonstrate that a lookahead policy with dynamically adjusted horizon outperforms the other two policies in terms of estimation accuracy, which is up to 19% higher in some instances.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )
查看更多>>摘要：A continuous supply of used products ensures large-scale remanufacturing. Manufacturers can delegate used product collection to third-party collectors (3PCs) that provide a trade-old-for-cash (TOC) program, in addition to collecting used products through a trade-old-for-new (TON) program. However, few studies have investigated the interactions between collection delegation and channel structure in a supply chain. To fill this gap, we develop game-theoretic models in a supply chain under traditional retail channel and dual-channel structures to explore whether and when the manufacturer adopts the collection delegation policy and examine the optimal channel choice for trade-ins. Our finding shows that the manufacturer always benefits from collection delegation, but the retailer would be worse off from such delegation in certain cases. To be specific, under the retail channel structure, collection delegation has no impact on the retailer when the salvage value of used products is relatively low, whereas it hurts the retailer when the salvage value is relatively high. However, under the dual-channel structure, collection delegation never affects the retailer. Moreover, we find that the manufacturer's channel choice depends on the consumer acceptance of the direct channel and the salvage value of used products. We further consider the case that the manufacturer does not introduce the TON programs to explore the effects of TON and the case that the new and remanufactured products are sold at different retail prices to examine the equilibrium strategies. Our results can provide useful managerial insights for decisions-makers who face the choice of collection delegation under different channel structures. (C) 2022 Elsevier B.V. All rights reserved.
NSTL
Elsevier