Purpose Marine transportation has been faced with an increasing demand for containerized cargo during the past decade. Marine container terminals (MCTs), as the facilities for connecting seaborne and inland transportation, are expected to handle the increasing amount of containers, delivered by vessels. Berth scheduling plays an important role for the total throughput of MCTs as well as the overall effectiveness of the MCT operations. This study aims to propose a novel island-based metaheuristic algorithm to solve the berth scheduling problem and minimize the total cost of serving the arriving vessels at the MCT. Design/methodology/approach A universal island-based metaheuristic algorithm (UIMA) was proposed in this study, aiming to solve the spatially constrained berth scheduling problem. The UIMA population was divided into four sub-populations (i.e. islands). Unlike the canonical island-based algorithms that execute the same metaheuristic on each island, four different population-based metaheuristics are adopted within the developed algorithm to search the islands, including the following: evolutionary algorithm (EA), particle swarm optimization (PSO), estimation of distribution algorithm (EDA) and differential evolution (DE). The adopted population-based metaheuristic algorithms rely on different operators, which facilitate the search process for superior solutions on the UIMA islands. Findings The conducted numerical experiments demonstrated that the developed UIMA algorithm returned near-optimal solutions for the small-size problem instances. As for the large-size problem instances, UIMA was found to be superior to the EA, PSO, EDA and DE algorithms, which were executed in isolation, in terms of the obtained objective function values at termination. Furthermore, the developed UIMA algorithm outperformed various single-solution-based metaheuristic algorithms (including variable neighborhood search, tabu search and simulated annealing) in terms of the solution quality. The maximum UIMA computational time did not exceed 306 s. Research limitations/implications Some of the previous berth scheduling studies modeled uncertain vessel arrival times and/or handling times, while this study assumed the vessel arrival and handling times to be deterministic. Practical implications The developed UIMA algorithm can be used by the MCT operators as an efficient decision support tool and assist with a cost-effective design of berth schedules within an acceptable computational time. Originality/value A novel island-based metaheuristic algorithm is designed to solve the spatially constrained berth scheduling problem. The proposed island-based algorithm adopts several types of metaheuristic algorithms to cover different areas of the search space. The considered metaheuristic algorithms rely on different operators. Such feature is expected to facilitate the search process for superior solutions.
more »
« less
This content will become publicly available on February 22, 2025
An Efficient Solving Approach for the p‐Dispersion Problem Based on the Distance‐Based Spatially Informed Property
The
- NSF-PAR ID:
- 10492043
- Publisher / Repository:
- Wiley-Blackwell
- Date Published:
- Journal Name:
- Geographical Analysis
- ISSN:
- 0016-7363
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract Mixed-Integer Linear Programming (MILP) plays an important role across a range of scientific disciplines and within areas of strategic importance to society. The MILP problems, however, suffer from
combinatorial complexity . Because of integer decision variables, as the problem size increases, the number of possible solutions increasessuper-linearly thereby leading to a drastic increase in the computational effort. To efficiently solve MILP problems, a “price-based” decomposition and coordination approach is developed to exploit 1. the super-linear reduction of complexity upon the decomposition and 2. the geometric convergence potential inherent to Polyak’s stepsizing formula for the fastest coordination possible to obtain near-optimal solutions in a computationally efficient manner. Unlike all previous methods to set stepsizes heuristically by adjusting hyperparameters, the key novel way to obtain stepsizes is purely decision-based: a novel “auxiliary” constraint satisfaction problem is solved, from which the appropriate stepsizes are inferred. Testing results for large-scale Generalized Assignment Problems demonstrate that for the majority of instances, certifiably optimal solutions are obtained. For stochastic job-shop scheduling as well as for pharmaceutical scheduling, computational results demonstrate the two orders of magnitude speedup as compared to Branch-and-Cut. The new method has a major impact on the efficient resolution of complex Mixed-Integer Programming problems arising within a variety of scientific fields. -
more » « less
We aim to preserve a large amount of data generated inside
base station-less sensor networks (BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration); as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP:d atap reservationp roblem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design a minimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit.In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of the failure of the DPG-1. It is due to the packet dropping by the selfish nodes that manipulate the AMD technique. We then design a data preservation game DPG-2 for DPP that traces and punishes manipulative nodes in the BSN. We show that DPG-2 delivers dominant strategies for truth-telling nodes and achieves provably optimal data preservation with cheat-proof guarantees. Via extensive simulations under different network parameters and dynamics, we show that our games achieve system-wide data preservation solutions with optimal energy cost while enforcing truth-telling of sensor nodes about their private cost types. One salient feature of our work is its integrated game theory and network flows approach. With the observation of flow level sensor node behaviors provided by the network flows, our proposed games can synthesize “microscopic” (i.e., selfish and local) behaviors of sensor nodes and yield targeted “macroscopic” (i.e., optimal and global) network performance of data preservation in the BSN.
-
more » « less
Abstract Patterns of
δ 18O andδ 2H in Earth's precipitation provide essential scientific data for use in hydrological, climatological, ecological and forensic research. Insufficient global spatial data coverage promulgated the use of gridded datasets employing geostatistical techniques (isoscapes) for spatiotemporally coherent isotope predictions. Cluster‐based isoscape regionalization combines the advantages of local or regional prediction calibrations into a global framework. Here we present a revision of a Regionalized Cluster‐Based Water Isotope Prediction model (RCWIP2) incorporating new isotope data having extensive spatial coverage and a wider array of predictor variables combined with high‐resolution gridded climatic data. We introduced coupling ofδ 18O andδ 2H (e.g.,d ‐excess constrained) in the model predictions to prevent runaway isoscapes when each isotope is modelled separately and cross‐checked observed versus modelledd ‐excess values. We improved model error quantification by adopting full uncertainty propagation in all calculations. RCWIP2 improved the RMSE over previous isoscape models by ca. 0.3 ‰ forδ 18O and 2.5 ‰ forδ 2H with an uncertainty <1.0 ‰ forδ 18O and < 8 ‰ forδ 2H for most regions of the world. The determination of the relative importance of each predictor variable in each ecoclimatic zone is a new approach to identify previously unrecognized climatic drivers on mean annual precipitationδ 18O andδ 2H. The improved RCWIP2 isoscape grids and maps (season, monthly, annual, regional) are available for download athttps://isotopehydrologynetwork.iaea.org . -
more » « less
Abstract Conserving large carnivores requires protecting landscape spaces that encompass all spatiotemporal scales of their movement. Large carnivores normally roam widely, but habitat loss and fragmentation can constrain their movement in ways that restrict access to resources and increase encounters with humans and potential conflict. Facilitating carnivore population coexistence with humans across landscapes requires conservation plans informed by patterns of carnivore space use, particularly at the human–wildlife interface.
We sought to understand lion space use in Laikipia, Kenya. We conducted a path‐selection function analysis using GPS collar data from 16 lions to assess patterns of space use across a range of spatial scales (sedentary to home range expanses; 0, 12.5, 25 and 50 km) and temporal scales (day, dusk, night and dawn). Path‐selection results were then incorporated into space use maps.
We found that most landscape features influenced path‐selection at the broadest spatial scale (50 km), representative of home range‐wide movement, thereby demonstrating a landscape‐wide human impact on lion space use. We also detected sub‐diurnal variation in lion path‐selection which revealed limited space use during daylight hours and increased space use overnight.
Our results highlight that optimal support for human–lion coexistence should be temporally adaptive at sub‐diurnal scales. Furthermore, spatial approaches to lion conservation may be better generalized at broad spatial scales so that land management plans can account for home range patterns in lion space use.
