Search

This article proposes a hierarchical multiobjective heuristic (HMOH) to optimize printed-circuit board assembly (PCBA) in a single beam-head surface mounter. The beam-head surface mounter is the core facility in a high-mix and low-volume PCBA line. However, as a large-scale, complex, and multiobjective combinatorial optimization problem, the PCBA optimization of the beam-head surface mounter is still a challenge. This article provides a framework for optimizing all the interrelated objectives, which has not been achieved in the existing studies. A novel decomposition strategy is applied. This helps to closely model the real-world problem as the head task assignment problem (HTAP) and the pickup-and-place sequencing problem (PAPSP). These two models consider all the factors affecting the assembly time, including the number of pickup-and-place (PAP) cycles, nozzle changes, simultaneous pickups, and the PAP distances. Specifically, HTAP consists of the nozzle assignment and component allocation, while PAPSP comprises place allocation, feeder set assignment, and place sequencing problems. Adhering strictly to the lexicographic method, the HMOH solves these subproblems in a descending order of importance of their involved objectives. Exploiting the expert knowledge, each subproblem is solved by an elaborately designed heuristic. Finally, the proposed HMOH realizes the complete and optimal PCBA decision making in real time. Using industrial PCB datasets, the superiority of HMOH is elucidated through comparison with the built-in optimizer of the widely used Samsung SM482.

In the traditional single-machine scheduling problem with uncertain processing time, distributionally robust optimization models are established in situations where the distribution information is not known exactly. One well-studied robust optimization method used in scheduling is the distributionally β -robust optimization technique. The goal of this technique is to maximize the probability that the total flow time of the job sequence does not exceed the predetermined target level T . However, it is possible that the excess value of the total flow time beyond the target T may be incredibly large, and therefore it is necessary to consider the optimized excess value. To address this concern, two new target-based risk measures are introduced. First, target-oriented CVaR, the worst-case conditional value-at-risk (CVaR) is used to minimize the excess value beyond T , which accounts for both the excess probability and the excess value. Second, the essential riskiness index (ERI) is extended to a multi-piecewise linear function for excess value control in single-machine scheduling problems. To obtain a tractable closed-form solutions of the risk measures, the CVaR-based measure is decomposed into an assignment problem and a second-order cone programming problem, and the ERI is converted to its equivalent semi-definite programming and second-order cone counterparts. To efficiently solve the risk measures for single-machine scheduling, a bisection search algorithm and a Benders decomposition algorithm are designed. In the numerical analysis, the excess value and the probability are investigated with respect to two distributions, namely the two-point distribution and the truncated normal distribution. The experiment design also considers different ranges of expectation and variance, tolerance levels, and problem scales. It is discovered that the CVaR and ERI-based methods are always better than the distributionally β -robust scheduling approach in terms of excess value.

The ongoing quest for transportation electrification with the massive proliferation of EV charging stations (EVCSs) will deepen the interaction and require the further coordination of coupled power and transportation networks (PTN). The individually-owned EVCSs located in an urban transportation network (UTN) will compete using price signals to maximize their respective payoffs. In this paper, a multi-agent deep reinforcement learning (MA-DRL) method is proposed to model the pricing game in UTN and determine the optimal charging prices for a single EVCS. The EVCS charging demand is first analyzed using a modified user equilibrium traffic assignment problem (UE-TAP) with elastic traveling demands and different charging prices. The price competition problem is then formulated as a game with incomplete information in which the market environment is very complex due to nonlinear traffic assignments. Thus, the MA-DRL approach is proposed to learn the charging pricing strategies of multiple EVCSs and approximate the Nash Equilibrium (NE) of the pricing game using the incomplete information. The proposed solution will determine the optimal pricing strategies for an EVCS in UTN. The case studies on a 24-node Sioux-Falls network and real-world Xian city are conducted to verify the effectiveness of the proposed approach.

A fundamental component of the game theoretic approach to distributed control is the design of local utility functions. Relative to resource allocation problems that are additive over the resources, Part I showed how to design local utilities so as to maximize the associated performance guarantees [1], which we measure by the price of anarchy. The purpose of the present manuscript is to specialize these results to the case of submodular, covering, and supermodular problems. In all these cases we obtain tight expressions for the price of anarchy that often match or improve the guarantees associated to state-of-the-art approximation algorithms. Two applications and corresponding numerics are presented: the vehicle-target assignment problem and a coverage problem arising in wireless data caching.

Motivated by evidence that parliament seatings are relevant for decision making, we consider the problem to assign seats in a parliament to members of parliament. We prove that the resulting seating assignment problem is strongly NP-hard in several restricted settings. We present a Mixed Integer Programming formulation of the problem, we describe two families of valid inequalities and we discuss symmetry-breaking constraints. Further, we design a heuristic. Finally, we compare the outcomes of the Mixed Integer Programming formulation with the outcomes of the heuristic in a computational study.

Problem definition: We consider an intermediary’s problem of dynamically matching demand and supply of heterogeneous types in a periodic-review fashion. Specifically, there are two disjoint sets of demand and supply types, and a reward for each possible matching of a demand type and a supply type. In each period, demand and supply of various types arrive in random quantities. The platform decides on the optimal matching policy to maximize the expected total discounted rewards, given that unmatched demand and supply may incur waiting or holding costs, and will be fully or partially carried over to the next period. Academic/practical relevance: The problem is crucial to many intermediaries who manage matchings centrally in a sharing economy. Methodology: We formulate the problem as a dynamic program. We explore the structural properties of the optimal policy and propose heuristic policies. Results: We provide sufficient conditions on matching rewards such that the optimal matching policy follows a priority hierarchy among possible matching pairs. We show that those conditions are satisfied by vertically and unidirectionally horizontally differentiated types, for which quality and distance determine priority, respectively. Managerial implications: The priority property simplifies the matching decision within a period, and the trade-off reduces to a choice between matching in the current period and that in the future. Then the optimal matching policy has a match-down-to structure when considering a specific pair of demand and supply types in the priority hierarchy.

Optimizing all the objectives of the printed circuit board assembly (PCBA) optimization in a multifunctional placer remains a formidable challenge till now. This article converts the original PCBA optimization problem to a newly defined component allocation problem, which decides the component-type handled by each head per pickup-and-place (PAP) cycle. The component allocation problem is a quadratic 3-D assignment problem (Q3AP) and effectively combines the optimization of all the main objectives. It is possible that one head stays idle, so the assigning 2-D locations are uncertain. We propose the cell division genetic algorithm (CDGA) to solve such a complex Q3AP. The CDGA allocates a component cell as the basic unit. Each of the first-generation component cells contains the mounting points of the same type. A cell chromosome decoding heuristic is designed to determine the next assigning head. By doing so, the problem dimension is reduced, so the conventional GA can be used for searching the optimal component allocation formed by the current-generation cells. When a better allocation can no longer be found by allocating the current cells, the cell division operation is performed to divide each cell into two new cells. The new cells are used in the next round of GA searching, which further optimizes the allocation from two perspectives: better balancing the minimization of nozzle changes and PAP cycles, more flexibly maximizing the simultaneous pickups with the uncertain locations. The CDGA works continuously until the current cells cannot bring any improvement. In simulations and experiments using the industrial samples, the proposed algorithm significantly reduces the PCBA time compared to two recent studies and the built-in optimizer of the widely used multifunctional placer, Hanwha SM482 PLUS, which demonstrates its effectiveness and superiority.

The objective of fuzzy assignment problem is to find the least assignment fuzzy cost (maximum fuzzy profit) of workers with varying degree of skills to job. To attain the objective in this article, an approach involving modified best candidate method has been used to solve Hexagonal fuzzy assignment problem. To order the hexagonal fuzzy numbers Robust’s Ranking technique is applied. We examine a numerical example by using new method and compute by existing two methods. Also we compare the optimal solutions among this new method and two existing method .The proposed method is a systematic procedure, easy to apply for solving fuzzy assignment problem.

To meet the demands of every customer by supplying the products at the limited time by maximizing the profit is a dream for many companies. By choosing the best candidate among the other candidates and effectively reaching the optimal solution with a new modified approach using Best Candidate Method in Fuzzy assignment problems. In this paper the author solve Fuzzy assignment problem in which Triangular and Trapezoidal fuzzy numbers are used. Robust Ranking Technique is used for the ranking of fuzzy numbers.

We study thetruthful facility assignmentproblem, where a set of agents with private most-preferred points on a metric space have to be assigned to facilities that lie on the metric space, under capacity constraints on the facilities. The goal is to produce such an assignment that minimizes the social cost, i.e., the total distance between the most-preferred points of the agents and their corresponding facilities in the assignment, under the constraint of truthfulness, which ensures that agents do not misreport their most-preferred points. We propose aresource augmentation framework, where a truthful mechanism is evaluated by its worst-case performance on an instance with enhanced facility capacities against the optimal mechanism on the same instance with the original capacities. We study a well-known mechanism, Serial Dictatorship, and provide an exact analysis of its performance. Among other results, we prove that Serial Dictatorship has approximation ratio$$g/(g-2)$$g/(g-2)when the capacities are multiplied by any integer$$g \ge 3$$g≥3. Our results suggest that with a limited augmentation of the resources we can achieve exponential improvements on the performance of the mechanism and in particular, the approximation ratio goes to 1 as the augmentation factor becomes large. We complement our results with bounds on the approximation ratio of Random Serial Dictatorship, the randomized version of Serial Dictatorship, when there is no resource augmentation.

We consider the NP-hard integer three-index axial assignment problem. Strategies for combining feasible solutions of the problem are investigated. Combining can be used as a supplement to heuristic or approximate solution algorithms instead of the generally accepted step of choosing the record among the feasible solutions found. The results of computational experiments are presented that demonstrate the promising nature of the approach proposed.

We examine a service system that matches jobs and candidates with different ability levels. A candidate’s ability will affect the possibility of obtaining a high return on a job assignment. Based on the property that the jobs to be assigned to a candidate are substituted in an assignment problem, we propose a novel random parameter generating process to demonstrate that the expected reward increases with the ability level of a candidate at a diminishing rate. This observation is consistent with the classic result in process flexibility literature that a little flexibility (i.e., ability level) can capture the most benefit. Our observations can help a company decide the proper level of ability.

We consider the problem of planning the annual timetable for all freight trains in Germany simultaneously. That is, for each train, construct a slot through the network such that no two slots of different trains have a conflict. We denote this task by the Train Path Assignment Problem (TPAP) and present a column generation approach where iteratively, the set of possible slots grows. In each iteration, we look for a maximum subset without any conflicts. Modelling the slots as vertices joint by an edge if they have a conflict, this problem is the Maximum Independent Set problem (MIS). Due to the many slots that are constructed, hence variables that are generated, we deal with large scale MIS instances. Therefore, the MIS is solved heuristically with a local search algorithm called Conflict Resolving (CR) that is tailored to the specially structured instances from the application. CR iteratively perturbs the current solution in order to leave local optima and then repeatedly improves the solution by replacing k − 1 solution vertices by k non-solution vertices. These steps are embedded in a simulated annealing framework. In this paper, we present the column generation approach and numerically compare three MIS solution methods, CR, a MIP solver and Iterated Local Search (ILS), a state-of-the-art MIS heuristics. It turns out that CR performs best for the instances from real-world timetabling, and is also comparable to the ILS on MIS benchmark instances. With this approach, we can solve the TPAP for more than 5000 freight trains.

To exploit the power domain diversity, heterogeneous non-orthogonal multiple access (NOMA) networks improve the spectrum efficiency for Internet of Things (IoT). For video traffic transmission, we formulate a resource allocation and assignment problem as a mixed integer non-linear programming (MINLP) subject to video encoding characteristics, maximum number of accessed devices, max-min fairness criterion, and total available energy of each device. To solve the resource allocation and assignment problem over heterogeneous NOMA networks, two subproblems are formulated, i.e., a packet assignment subproblem for video traffic and a joint device allocation and power control subproblem. Firstly, the joint device allocation and power control subproblem is transformed into a bi-convex programming with successive convex approximation (SCA) method. Then, an optimal device allocation and power control solution is obtained via dual decomposition method. Finally, a heuristic packet assignment algorithm via greedy method is presented for video transmission traffic. In numerical simulation, we can see that the proposed algorithm guarantees the max-min fairness among different devices, and improves the minimum and average video transmission quality over heterogeneous NOMA networks.

We consider assignment problems where individuals are to be assigned at most one indivisible object and monetary transfers are not allowed. We provide a characterization of assignment rules that are Pareto efficient, non-bossy, and implementable in obviously strategy-proof (OSP) mechanisms. As corollaries of our result, we obtain a characterization of OSP-implementable fixed priority top trading cycles (FPTTC) rules, hierarchical exchange rules, and trading cycles rules. Troyan (2019) provides a characterization of OSP-implementable FPTTC rules when there are equal number of individuals and objects. Our result generalizes this for arbitrary values of those.

Purpose More and more work zone projects come with the needs of new construction and regular maintenance-related investments in transportation. Work zone projects can have many significant impacts socially, economically and environmentally. Minimizing the total impacts of work zone projects by optimizing relevant schedules is extremely important. This study aims to analyze the impacts of scheduling long-term work zone activities. Design/methodology/approach Optimal scheduling of the starting dates of each work zone project is determined by developing and solving using a bi-level genetic algorithm (GA)–based optimization model. The upper level sub-model is to minimize the total travel delay caused by work zone projects over the entire planning horizon, whereas the lower level sub-model is a traffic assignment problem under user equilibrium condition with elastic demand. Findings Sioux Falls network is used to develop and test the proposed GA-based model. The average and minimum total travel delays (TTDs) over generations of the proposed GA algorithm decrease very rapidly during the first 20 generations of the GA algorithm; after the 20th generations, the solutions gradually level off with a certain level of variations in the average TTD, showing the capability of the proposed method of solving the multiple work zone starting date optimization problem. Originality/value The proposed model can effectively identify the near-optimal solution to the long-term work zone scheduling problem with elastic demand. Sensitivity analysis of the impact of the elastic demand parameter is also conducted to show the importance of considering the impact of elastic demand parameter.

We consider the NP-hard integer three-index axial assignment problem. The task of optimal combination of the pairs of feasible solutions of the problem is posed, and a linear complexity algorithm for its solution is constructed. This algorithm can be used as a supplement to heuristic or approximate algorithms for the three-index assignment problem for post-processing the obtained approximate solutions of the problem. The results of computational experiments, which demonstrate the promising nature of our approach, are presented.

In the Quadratic Assignment Problem (QAP), facilities are assigned to sites in order to minimize interactions between pairs of facilities. Although easy to define, it is among the hardest problems in combinatorial optimization, due to its non-linear nature. After decades of research on the QAP, many variants of this problem arose to deal with different applications. Along with the QAP, we consider four variants – the Quadratic Bottleneck Assignment Problem, the Biquadratic Assignment Problem, the Quadratic Semi-Assignment Problem, and the Generalized QAP – and develop a single framework to solve them all. Our parallel memetic iterated tabu search (PMITS) extends the most successful heuristics to solve the QAP. It combines the diversification phase of generating new local optima found after solutions modified by a new crossover operator that is biased towards one of the parents, with the intensification phase of an effective tabu search which uses a simplified tabu list structure to reduce the number of parameters and a new long-term memory that saves solutions previously visited to speed up the search. Solutions are improved concurrently using parallelism, and a convergence criterion determines whether the search stops according to the best solutions in each parallel search. Computational experiments using the hardest benchmark instances from the literature attest the effectiveness of the PMITS, showing its competitiveness when compared to the state-of-the-art methods, sequential and parallel, to solve the QAP. We also show that PMITS significantly outperforms the best methods found for all four variants of the QAP, significantly updating their literature.

In this paper, a multi-objective faculty course allocation problem with result analysis and feedback analysis based on uncertain preferences mathematical model is presented. To deal with an uncertain model, three different ranking criteria are being used to develop: a) Expected value, b) Optimistic value, c) Dependent optimistic value criterion. These mathematical models are transformed into their corresponding deterministic forms using the basic concepts of uncertainty theory. The deterministic model of DOCM consists of fractional objectives which are converted into their linear form using Charnes and Cooper’s transformation. These deterministic formulations MOFCAP are converted into a single objective problem by using the fuzzy programming technique with linear and exponential membership functions. Further, the single objective problem for all the defined models is solved in the Lingo 18.0 software to derive the Pareto-optimal solution. The sensitivity of the models is also performed to examine the variation in the objective function due to the variation in parameters. Finally, a numerical example is given to exhibit the application and algorithm of the models.

To improve the radio spectral efficiency for 5G and beyond, novel radio access techniques need to be designed to accommodate unprecedented number of connected devices, and nonorthogonal multiple access (NOMA) has become a promising candidate. Additionally, power allocation and NOMA-secondary user (SU) assignment technology is an efficient way to enhance the resource utilization efficiency at the power domain and the spectral domain for underlaying cognitive NOMA networks. In this article, first, a joint power allocation and SU assignment problem is formulated for the NOMA downlink transmission in an underlaying cognitive radio network. The worst-case achievable rate for the NOMA-SU is maximized. To solve this mixed-integer nonlinear programming problem, we divide the original optimization problem into two subproblems: NOMA-SU assignment and power allocation. Next, a heuristic algorithm is adopted to solve the NOMA-SU assignment subproblem, and successive convex approximation based method is utilized to design a suboptimal power allocation algorithm. Furthermore, an alternative joint NOMA-SU assignment and power allocation scheme are proposed with its average computational complexity analysis given. Finally, numerical results show that the total throughput for the proposed algorithm outperforms more than 30% compared with an existing benchmark scheme at least.

We study multitasking scheduling and due-window assignment problems in a single machine, which can be found in various application domains. In multitasking environment, unfinished job always interrupts in-processing job. In common due window assignment, the aim is to find optimal due window to minimise the value of the earliness and tardiness penalty. In this paper, we study two problems, where the objective of the first problem is minimise the earliness, tardiness, due-window starting time, and due-window size costs, the objective of the second problem is minmax common due-date with completion time penalty, then we obtain some analytical properties and provide polynomial time solutions. Finally, the experimental results show that the proposed methods are effective.

We propose a new graph model of transportation on a single-line railway section. Based on a given freight-train delivery schedule, we construct an acyclic graph with vertices denoting deliveries and arcs indicating the possibility of successive implementation of these deliveries by some locomotive. This model of the problem permits applying static graph algorithms to find an optimal locomotive assignment plan. The search for a solution of the problem without time constraints on the locomotives is reduced to finding a minimal path cover of an acyclic graph. Each path in the cover corresponds to a sequence of deliveries carried out by one locomotive. If there are temporary constraints on the locomotives (maintenance breaks), not all paths in the cover can remain valid: for some locomotives, none of the established delivery sequences can be performed from start to finish. In this case, one more solution stage is added, at which the cover is transformed in such a way that all new paths describe a sequence of deliveries that can be carried out by a given set of locomotives under given time constraints.

We consider the patient-to-bed assignment problem that arises in hospitals. Both emergency patients who require hospital admission and elective patients who have had surgery need to be found a bed in the most appropriate ward. The patient-to-bed assignment problem arises when a bed request is made, but a bed in the most appropriate ward is unavailable. In this case, the next-best decision out of a many alternatives has to be made, according to some suitable decision making algorithm. We construct a Markov chain to model this problem in which we consider the effect on the length of stay of a patient whose treatment and recovery consists of several stages, and can be affected by stays in or transfers to less suitable wards. We formulate a dynamic program recursion to optimise an objective function and calculate the optimal decision variables, and discuss simulation techniques that are useful when the size of the problem is too large. We illustrate the theory with some numerical examples.

The conventional assignment problem is unable to handle scenarios that may arise due to different working modes of machines leading to multiple cost and time entries corresponding to a job–machine pair. The present article deals with this problem and models it as a multi-choice bi-objective assignment problem, the two objectives being assignment cost and bottleneck time. Two different solution procedures are presented based on the Decision-Maker's (DM's) preference structure. First, when the DM provides his/her preference structure as goals, a solution methodology is proposed using goal programming and its different multi-choice variants. In the second case, when no preference is provided by the DM, a two-step approach is presented that iteratively solves a multi-choice cost-minimizing assignment problem to obtain all Pareto-optimal time–cost pairs and finally, based on the Technique for Order Preference by Similarity to the Ideal Solution (TOPSIS), a single efficient pair is obtained. The algorithm is successfully implemented using the CPLEX® optimization package and tested on various test problems.

This study focused on vital resources at port container terminals such as quay cranes and dockworkers. We studied the impact of incorporating the dockworker assignment problem (DWAP) into the quay crane assignment problem (QCAP). The aim of this study was to formulate and solve an integrated model for QCAP and DWAP, with the objective of minimizing the total costs of dockworkers, by optimizing workers’ assignment, so that the ships’ costs due to the time spent in the port are not increased. We proposed an integrated solution approach to the studied problem. Our proposed model has been validated on an adequate number of instances based on the real data. Obtained solutions were compared with the solutions obtained by the traditional sequential approach. It was demonstrated that, for all solved instances, our proposed integrated approach resulted in a reduction in the total costs of dockworkers. The major contribution of this study is that this is the first time that these two problems were modeled together. The obtained results show significant savings in the overall costs.

In this paper, we extend the purely dual formulation that we recently proposed for the three-dimensional assignment problems to solve the more general multidimensional assignment problem. The convex dual representation is derived and its relationship to the Lagrangian relaxation method that is usually used to solve multidimensional assignment problems is investigated. Also, we discuss the condition under which the duality gap is zero. It is also pointed out that the process of Lagrangian relaxation is essentially equivalent to one of relaxing the binary constraint condition, thus necessitating the auction search operation to recover the binary constraint. Furthermore, a numerical algorithm based on the dual formulation along with a local search strategy is presented. The simulation results show that the proposed algorithm outperforms the traditional Lagrangian relaxation approach in terms of both accuracy and computational efficiency.

The generalized assignment problem (GAP) is an open problem in which an integer k is given and one wants to assign k ′ agents to k k ′ ≤ k jobs such that the sum of the corresponding cost is minimal. Unlike the traditional K -cardinality assignment problem, a job can be assigned to many, but different, agents and an agent may undertake several, but different, jobs in our problem. A network model with a special structure of GAP is given and an algorithm for GAP is proposed. Meanwhile, some important properties of the GAP are given. Numerical experiments are implemented, and the results indicate that the proposed algorithm can globally and efficiently optimize the GAP with a large range cost.

In this paper, we develop a new bi-objective model for dynamic weapon-target assignment problem. We consider that the initial weapon assignment plan of defense is disrupted during engagement because of a destroyed air target, breakdown of a weapon system or a new incoming air target. The objective functions are defined as the maximization of probability of no-leaker and the maximization of stability in engagement order of weapon systems. Stability is defined as assigning same air target in sequence in engagement order of a weapon system so that reacquisition and re-tracking of air target are not required by sensors. We propose a new solution procedure to generate updated assignment plans by maximizing efficiency of defense while maximizing stability through swapping weapon engagement orders. The proposed solution procedure generates non-dominated solutions from which defense can quickly choose the most-favored course of action. We solve a set of representative problems with different sizes and present computational results to evaluate effectiveness of the proposed approach.

A zero-one quadratic assignment model has been proposed for dealing with the storage location assignment problem when there are weight constraints. Our analysis shows that operations can be improved using our model. When comparing the strategy currently used in a real-life company with the designed model, we found that the new placement of products allowed a reduction of up to 22% on the picking distance. This saving is higher than that achieved with the creation of density zones, a procedure commonly used to deal with weight constraints, according to the literature. (original abstract)

Formation flight of multiple unmanned aerial vehicles (UAV) is in an active development and spreads more widely in many areas of human activity nowadays. One of the basic problems in their application is a formation assignment and formation control. Many authors work in the direction of coordination control and multiple UAV path planning, discarding problems of collision avoidance when following the trajectories to the assigned target positions in dense formations. A novel formulation of the collision-aware formation assignment problem and a centralized turn-based algorithm to solve the problem of realizability of assignment and provide the optimal solution by several criteria is proposed in this paper. Besides the formation assignment solution, the priority of movement to avoid deadlocks is obtained. The approach consists of three stages: 1) obtaining of solution of assignment problem; 2) validation of realizability of optimal solution with simultaneous determination of acceptable turn order; 3) in case of unrealizability the next optimal solution is being validated. The proposed algorithm is validated with simulation results, which confirm the possibility of real time application.

Traffic Assignment Problem (TAP) is a critical issue for transportation and mobility models that deals mainly with the calculus and delivery of best-cost routes for the trips in a traffic network. It is a computationally complex problem focused on finding user equilibrium (UE) and system optimum (SO). The Traffic Weighted Multi-Maps (TWM) technique offers a new perspective for TAP calculus, based on routing decisions using different traffic network views. These TWM are complementary cost maps that combine physical traffic networks, traffic occupation data, and routing policies. This paper shows how evolutionary algorithms can find optimal cost maps that solve TAP from the SO perspective, minimizing total travel time and providing the best-cost routes to vehicles. Several strategies are compared: a baseline algorithm that optimizes the whole network and two algorithms based on extended k-shortest path mappings. Algorithms are analyzed following a simulation-optimization methodology over synthetic and real traffic networks. Obtained results show that TWM algorithms generate solutions close to the static UE traffic assignment methods at a reasonable computational cost. A crucial aspect of TWM is its good performance in terms of optimal routing at the system level, avoiding the need for continuous route calculus based on traffic status data streaming.

This paper provides an extensive review of the popular multi-objective optimization algorithm NSGA-II for selected combinatorial optimization problems viz. assignment problem, allocation problem, travelling salesman problem, vehicle routing problem, scheduling problem, and knapsack problem. It is identified that based on the manner in which NSGA-II has been implemented for solving the aforementioned group of problems, there can be three categories: Conventional NSGA-II, where the authors have implemented the basic version of NSGA-II, without making any changes in the operators; the second one is Modified NSGA-II, where the researchers have implemented NSGA-II after making some changes into it and finally, Hybrid NSGA-II variants, where the researchers have hybridized the conventional and modified NSGA-II with some other technique. The article analyses the modifications in NSGA-II and also discusses the various performance assessment techniques used by the researchers, i.e., test instances, performance metrics, statistical tests, case studies, benchmarking with other state-of-the-art algorithms. Additionally, the paper also provides a brief bibliometric analysis based on the work done in this study. Web of Science 9 57791 57757

Task assignment is a critical technology for heterogeneous unmanned aerial vehicle (UAV) applications. Target precedence has typically been ignored in previous studies, such that it is possible to obtain a task assignment solution with an unreasonable target execution order. For this reason, a cooperative multiple task assignment problem with target precedence constraints (CMTAPTPC) model is proposed in this paper, which considers not only kinematic, resource, and task precedence constraints of the UAV, but also target precedence to achieve more realistic scenarios. In addition, a graph method is improved to detect and eliminate deadlocks in solutions that include target precedence constraints. We also introduced a waitable path coordination (WPC) algorithm to generate conflict-free flight paths. Unlike the traditional path elongation method, this method can reduce the number of path elongation operations and save the energy of UAVs. Based on the characteristics of the CMTAPTPC model, this study proposes a modified genetic algorithm that integrates the graph-based method and WPC algorithm to solve the task assignment problem. In the simulation, three problem-scale scenarios were designed, and the superior performance of the modified genetic algorithm was demonstrated by comparing it with a traditional genetic algorithm. Finally, a time series diagram shows the task assignment solution that meets all time constraints and illustrates the rationality of the WPC algorithm.

With rapid emergence of high-performance computing platforms, the availability of client big data and new machine learning techniques, the application domain of platform-based mobility services supports the research of new optimization techniques for discrete combinatorial optimization problems. Within this research field, particularly large-scale transportation domain specific problems, e.g. multi-vehicle-request matching and collaborative vehicle fleet routing problems are of high interest. In this contribution we present our novel combinatorial Deep Reinforcement Learning for solving symmetric and asymmetric multi-vehicle-request weighted assignment or matching problems by learning and predicting an efficient solution heuristic automatically. The solved assignment problem is characterized by defining different node classes for vehicles, requests and service stations. Our results contain algorithm benchmarks based on reproducible artificial data and statistical evaluations towards solution accuracy and efficiency with respect to different problem complexities. We contribute additional comparisons between different algorithms and heuristics such as naive Greedy, k-Regret and exact (globally optimal) solutions with the simplex method by the Mixed-Integer Programming (MIP) solver Cplex. Further, we compare the results with our model with respect to solution accuracy and efficiency We conclude that our proposed model solves the presented problem setting globally optimal up to an upper graph complexity bound defined via node degree. Furthermore, our results show that our proposed method outperforms all other algorithms with respect to the solution time required.

Many real-world networks such as freight, power and long distance transportation networks are represented as multi-source multi-sink stochastic flow network. The objective is to transmit flow successfully between the source and the sink nodes. The reliability of the capacity vector of the assigned components is used an indicator to find the best flow strategy on the network. The Components Assignment Problem (CAP) deals with searching the optimal components to a given network subject to one or more constraints. The CAP in multi-source multi-sink stochastic flow networks with multiple commodities has not yet been discussed, so our paper investigates this scenario to maximize the reliability of the capacity vector subject to an assignment budget. The mathematical formulation of the problem is defined, and a proposed solution based on genetic algorithms is developed consisting of two steps. The first searches the set of components with the minimum cost and the second searches the flow vector of this set of components with maximum reliability. We apply the solution approach to three commonly used examples from the literature with two sets of available components to demonstrate its strong performance.

This study focuses on the development of a mixed binary primal-dual bilinear model for multi-period bilevel network expansion planning under uncertainty, where pricing-based equilibrated strategic and operational decisions are to be made. The periodwise dependent parameters’ uncertainty is represented by a finite set of scenarios. Pricing-based equilibrium is required in the models to be optimized at the nodes of a multi-period scenario tree. Given the size of the models, it is unrealistic to seek an optimal solution. Several versions of a Stochastic Nested Decomposition matheuristic algorithm are presented for problem solving. Additionally, an approach based on a stagewise-related Stochastic Lagrangean Decomposition is also considered together with a Frank-Wolfe Progressive Hedging-based algorithm. The state step variables device is key for the performance of both approaches. The solution’s optimality gap is computed for three out of the four solution providers that are presented. An extension of the Toll Assignment Problem is considered as a pilot case. A broad computational experience is reported.

The airline crew scheduling problem is usually solved sequentially in two main steps because of its complexity: the crew pairing followed by the crew assignment. However, finding a globally optimal solution via the sequential approach may be impossible because the decision domain of the crew assignment problem is reduced by decisions made in the pairing problem. This study considers the crew scheduling problem in a personalized context where each pilot and copilot requests a set of preferred flights and vacations each month. We propose a model that completely integrates the crew pairing and personalized assignment problems to generate personalized monthly schedules for a given set of pilots and copilots simultaneously in a single optimization step. The model keeps the pairings in the two problems as similar as possible so that the propagation of perturbations arising during the operation is reduced. We develop an integrated algorithm that combines alternating Lagrangian decomposition, column generation, and dynamic constraint aggregation. We conduct computational experiments on a set of real instances from a major US carrier. Our integrated approach produces significant cost savings and better satisfaction of crew preferences compared with the traditional sequential approach.

The purpose of the work is to develop models and algorithms for optimizing matching in dynamically generated graphs of asymmetric relations in coordinated open systems of interacting agents with centralized and collective control. The dynamic asymmetric matching optimization problem arises here as a result of a compromise approximation of the mapping of the dynamic programming method onto a stream of known open assignment problems or several traveling salesmen. However, the branching alternatives presented in this way for independent tasks do not take into account the interdependence of real relationships between agents and their tasks, including their relationship to time. Ignoring the dependence of branching alternatives leads to a delay in the moment or to a loss in the quality of assignment of tasks to coordinated agents. The main idea of the proposed implementation of the principle known for effective control is to postpone the moment the final decision is made to the latest moment, taking into account the susceptibility of the system to local changes in state variables. The interdependence of states is revealed on the basis of the analysis of the correspondence of the graph of the current matching with the optimal solution on the subgraph of perfect matching. The transition between states is implemented by the incremental version of the reoptimization algorithm for solving linear problems of assigning the shortest replenishing path using the method. The space of search states is a dynamically generated bipartite sparse graph of alternatives for a combination of agents and tasks, represented by a list of arcs. To highlight the sets of changed arcs, it is proposed to supplement the weight of the arcs with the boundaries of the stability intervals of the solution, optionally formed in the background. By default, the weight of the modified arc matches the boundary of the stability interval. On each correction cycle of the lists of agents, tasks, and their associations, subsets of elements are selected for which reconsideration of matching is required. An enhanced condition for the selection of such elements is to go beyond the boundaries of the stability interval. In this case, the asymmetry of the assignment problem is taken into account by choosing the adjacency structure for the fraction of the graph with a minimum of vertices. As a result, the reaction time of procedures for solving the assignment problem is reduced by an order of magnitude.

This paper presents two models to investigate the traffic assignment problem. In the two models, the emission cost for gasoline vehicles (GVs) is considered. The credit schemes are considered in the constraint of the models. The operation costs for battery electric vehicles (BEVs) and GVs are also studied. Particularly, the constraints related to the credit schemes can be utilized to adjust the number of GVs and to promote growth of the number of BEVs, which is a novel idea that was not studied. Preliminary numerical experiments demonstrate that the models are effective and the extended distance limit of BEVs can raise the volume of BEVs under the condition that the unit traffic cost of BEVs is lower than GVs. Therefore, it is feasible to control the quantity of GVs by adjusting the total credit schemes, and it is viable to reduce the emission by enlarging the number of BEVs’ users.

This paper considers a generalized version of the planar storage location problem arising in the stowage planning for Roll-on/Roll-off ships. A ship is set to sail along a predefined voyage where given cargoes are to be transported between different port pairs along the voyage. We aim at determining the optimal stowage plan for the vehicles stored on a deck of the ship so that the time spent moving vehicles to enable loading or unloading of other vehicles (shifting), is minimized. We propose a novel mixed integer programming model for the problem, considering both the stowage and shifting aspect of the problem. An adaptive large neighborhood search (ALNS) heuristic with several new destroy and repair operators is developed. We further show how the shifting cost can be effectively evaluated using Dijkstra’s algorithm by transforming the stowage plan into a network graph. The computational results show that the ALNS heuristic provides high quality solutions to realistic test instances. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

This paper analyzes the integration of Non-Orthogonal Multiple Access (NOMA) in a Fog Radio Access Network (FRAN) architecture with limited fronthaul capacity. More precisely, it proposes methods for optimizing the resource allocation for the downlink of a NOMA-based FRAN with multiple resource blocks (RB). The resource allocation problem is formulated as a mixed-integer optimization problem, which determines the user-to-RB assignment, the power allocated to each RB, and the power split levels of the NOMA users served by each RB. The optimization problem maximizes a network-wide rate-based utility function subject to fronthaul-capacity constraints. The paper proposes a feasible decoupled solution for such a non-convex optimization problem using a three-step hybrid centralized/distributed approach, which in part relies on the edge-devices computation capabilities. The paper proposes and compares two distinct methods for solving the assignment problem, namely a Hungarian-based method, and a Multiple Choice Knapsack-based method. The power allocation to RBs and the NOMA power split optimization are solved using the alternating direction method of multipliers (ADMM). Simulations results illustrate the advantages of the proposed methods compared to different baseline schemes, including the conventional Orthogonal Multiple Access (OMA), for different utility functions and different network environments.

Device to device (D2D) communication has recently attracted a lot of attentions since it can significantly improve the system throughput and reduce the energy consumption. Indeed, the devices can communicate with each other in a D2D system, and the base station (BS) can share the spectrum with D2D users, which can efficiently improve the spectrum and energy efficiency. Nevertheless, spectrum sharing also raises the difficulty of resource allocation owing to the serious cochannel interference. To reduce the interference, the transmit power of the D2D pairs and BS to cellular users should be further optimized. In this paper, we consider the resource allocation problem of D2D networks involving the power allocation and subcarrier assignment. The resource allocation problem is formulated as a mixed integer programming problem which is difficult to solve. To reduce the computational complexity, the original problem is decomposed as two subproblems in terms of the subcarrier assignment and power allocation. For the subcarrier assignment problem, the particle swarm optimization (PSO) is adopted to solve it since the subcarrier assignment is an integer optimization problem, and it is difficult to be tackled using the traditional optimization approach. When the subcarrier assignment is fixed, there are only the power allocation variables in the original resource allocation problem. The difference of convex functions (DC) programming is adopted to solve the power allocation problem. Simulation results demonstrate the effectiveness of the proposed resource allocation scheme of D2D networks.

This research aims at solving the special case of multistate assignment problem. The problem includes many special characteristics which are not normally included in the assignment problem. There are many types and conditions of vehicles included in the planning and different road conditions of traveling, which would have different effects on fuel consumption, which is the objective function of the study. The proposed problem is determined as a large and complicated problem making the optimization software unable to find an optimal solution within the proper time. Therefore, the researchers had developed a method for determining the optimal solution by using particle swarm optimization (PSO) in which the methods were developed for solving the proposed problem. This method is called the modified particle swarm optimization (modified PSO). The proposed method was tested with three groups of tested instances, i.e., small, medium, and large groups. The computational result shows that, in small-sized and medium-sized problems, the proposed method performed not significantly different from the optimization software, and in the large-sized problems, the modified PSO method gave 3.61% lower cost than the cost generated from best solution generated from optimization software within 72 hours and it gave 11.03% better solution than that of the best existing heuristics published so far (differential evolution algorithm).