Discrete optimization

Select

1. A Gradient Descent Method for Estimating the Markov Chain Choice Model

Lei Fu, Dong-Dong Ge

Journal of the Operations Research Society of China 2023, 11 (2): 371-381. DOI: 10.1007/s40305-021-00365-6

摘要（1044）

PDF

In this paper, we propose a gradient descent method to estimate the parameters in a Markov chain choice model. Particularly, we derive closed-form formula for the gradient of the log-likelihood function and show the convergence of the algorithm. Numerical experiments verify the efficiency of our approach by comparing with the expectation-maximization algorithm. We show that the similar result can be extended to a more general case that one does not have observation of the no-purchase data.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

2. Disruption Recovery at Airports: Ground Holding, Curfew Restrictions and an Approximation Algorithm

Prabhu Manyem

Journal of the Operations Research Society of China 2021, 9 (4): 819-852. DOI: 10.1007/s40305-020-00338-1

摘要（2226）

PDF

We study disruptions at a major airport. Disruptions could be caused by bad weather, for example. Our study is from the perspective of the airport, the air services provider (such as air traffic control) and the travelling public, rather than from the perspective of a single airline. Disruptions cause flights to be subjected to ground holding, or they cause the flights to violate airport curfew hours. We consider curfew and arrival capacities applicable at a single airport. After proving that the problem is NP-hard, we present a polynomial time approximation algorithm based on the primal–dual schema and show that if the problem is feasible, the algorithm finds a feasible solution that is both within a certain additive bound and within a certain multiplicative factor of the optimal solution. The algorithm returns a solution mix of which flights suffer no delay, which ones to be ground-held and which ones may violate the curfew (and hence pay a curfew penalty). Computational results are positive; our heuristic outperforms the integer programming solver by a wide margin.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

3. Stable Matchings in the Marriage Model with Indifferences

Noelia Juarez, Jorge Oviedo

Journal of the Operations Research Society of China 2021, 9 (3): 593-617. DOI: 10.1007/s40305-020-00315-8

摘要（1263）

PDF

For the marriage model with indifferences, we define an equivalence relation over the stable matching set. We identify a sufficient condition, the closing property, under which we can extend results of the classical model (without indifferences) to the equivalence classes of the stable matching set. This condition allows us to extend the lattice structure over classes of equivalences and the rural hospital theorem.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

4. On the Stable Gani-Type Attainability Problem Controlled by Promotion at Maximum Entropy

Virtue Uwabomwen Ekhosuehi

Journal of the Operations Research Society of China 2021, 9 (3): 673-690. DOI: 10.1007/s40305-020-00301-0

摘要（1408）

PDF

This study considers the attainability problem in one-step for the stable Gani-type model controlled by promotion within the context of maximum entropy. The technique adopted involves formulating the attainability problem as a constrained optimisation problem wherein the objective is to maximise the Shannon entropy rate subject to certain constraints imposed by the attainable configuration and the sub-stochastic transition matrix. The principle of maximum entropy is used to obtain results that are consistent with the exponential representation of transition probabilities for manpower systems.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

5. The Continuous Knapsack Problem with Capacities

Huynh Duc Quoc, Nguyen Chi Tam, Tran Hoai Ngoc Nhan

Journal of the Operations Research Society of China 2021, 9 (3): 713-721. DOI: 10.1007/s40305-020-00298-6

摘要（1468）

PDF

We address a variant of the continuous knapsack problem, where capacities regarding costs of items are given into account. We prove that the problem is NP-complete although the classical continuous knapsack problem is solvable in linear time. For the case that there exists exactly one capacity for all items, we solve the corresponding problem in O(n log n) time, where n is the number of items.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

6. COVID-19 Pandemic with Human Mobility Across Countries

Cheng Zhang, Li-Xian Qian, Jian-Qiang Hu

Journal of the Operations Research Society of China 2021, 9 (2): 229-244. DOI: 10.1007/s40305-020-00317-6

摘要（2553）

PDF

This study develops a holistic view of the novel coronavirus(COVID-19) spread worldwide through a spatial–temporal model with network dynamics. By using a unique human mobility dataset containing 547 166 flights with a total capacity of 101 455 913 passengers from January 22 to April 24, 2020, we analyze the epidemic correlations across 22 countries in six continents and particularly the changes in such correlations before and after implementing the international travel restriction policies targeting different countries. Results show that policymakers should move away from the previous practices that focus only on restricting hotspot areas with high infection rates. Instead, they should develop a new holistic view of global human mobility to impose the international movement restriction. The study further highlights potential correlations between international human mobility and focal countries’ epidemic situations in the global network of COVID-19 pandemic.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

7. A Novel MILP Model for N-vehicle Exploration Problem

Guo-Jun Zhang, Jin-Chuan Cui

Journal of the Operations Research Society of China 2021, 9 (2): 359-373. DOI: 10.1007/s40305-019-00289-2

摘要（2080）

PDF

The N-vehicle exploration problem (NVEP) is a nonlinear discrete scheduling problem, and the complexity status remains open. To our knowledge, there is no literature until now employing mixed integer linear programming (MILP) technology to solve this problem except for Wang (J Oper Res Soc China 3(4):489–498, 2015). However, they did not give numerical experiments since their model existed strictly inequalities and the number of constraints was up to O(n³), which was inefficient to solve practical problems. This paper establishes a more concise MILP model, where the number of constraints is just O(n²). Therefore, the existing efficient MILP algorithms can be used to solve NVEP. Secondly, we provide some properties of N-vehicle problem and give three methods for cutting plane construction, which can increase the solving speed significantly. Finally, a numerical experiment is provided to verify the effectiveness and robustness for different instances and scales of acceleration techniques.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

8. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks

Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi

Journal of the Operations Research Society of China 2021, 9 (1): 99-117. DOI: 10.1007/s40305-018-0229-z

摘要（1287）

PDF

This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network. We call this problem as the integer inverse undesirable p-median location model. Exact combinatorial algorithms with $\mathcal{O}({p^2}\;n\;\log \;n)$ and $\mathcal{O}({p^2}(n\;\log \;n + n\;\log \;\eta {}_{\max }))$ running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms, respectively. Furthermore, it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in $\mathcal{O}({p^2}\;n\;\log \;n)$ time.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

9. Sufficient Conditions for Maximally Edge-Connected Hypergraphs

Lin-Ken Tong, Er-Fang Shan

Journal of the Operations Research Society of China 2021, 9 (1): 119-129. DOI: 10.1007/s40305-018-0224-4

摘要（1316）

PDF

The edge-connectivity of a graph or a hypergraph is defined as the minimum number of edges whose removal renders the graph or hypergraph disconnected. A graph or hypergraph is called maximally edge-connected if the edge-connectivity equals its minimum degree. In this paper, we show that some classical sufficient conditions for graphs to be maximally edge-connected can be generalized to hypergraphs.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

10. Linear Arboricity of Outer-1-Planar Graphs

Xin Zhang, Bi Li

Journal of the Operations Research Society of China 2021, 9 (1): 181-193. DOI: 10.1007/s40305-019-00243-2

摘要（1449）

PDF

A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once. Zhang et al. (Edge covering pseudoouterplanar graphs with forests, Discrete Math 312:2788-2799, 2012; MR2945171) proved that the linear arboricity of every outer-1-planar graph with maximum degree △ is exactly 「△/2」 provided that △ = 3 or △ ≥ 5 and claimed that there are outer-1-planar graphs with maximum degree △ = 4 and linear arboricity 「(△ + 1)/2」 = 3. It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2, and moreover, none of the above constraints on the crossing distance and crossing width can be removed. Besides, a polynomial-time algorithm for constructing a path-2-coloring (i.e., an edge 2-coloring such that each color class induces a linear forest, a disjoint union of paths) of such an outer-1-planar drawing is given.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

11. Performance Evaluation and Social Optimization of an Energy-Saving Virtual Machine Allocation Scheme Within a Cloud Environment

Xiushuang Wang, Jing Zhu, Shunfu Jin, Wuyi Yue, Yutaka Takahashi

Journal of the Operations Research Society of China 2020, 8 (4): 561-580. DOI: 10.1007/S40305-019-00272-x

摘要（309）

PDF

Achieving greener cloud computing is non-negligible for the open-source cloud platform. In this paper, we propose a novel virtual machine allocation scheme with a sleep-delay and establish a corresponding mathematical model. Taking into account the number of tasks and the state of the physical machine, we construct a two-dimensional Markov chain and derive the average latency of tasks and the energy-saving degree of the system in the steady state. Moreover, we provide numerical experiments to show the effectiveness of the proposed scheme. Furthermore, we study the Nash equilibrium behavior and the socially optimal behavior of tasks and carry out an improved adaptive genetic algorithm to obtain the socially optimal arrival rate of tasks. Finally, we present a pricing policy for tasks to maximize the social profit when managing the network resource within the cloud environment.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

12. On Semi-infinite Mathematical Programming Problems with Equilibrium Constraints Using Generalized Convexity

Bhuwan Chandra Joshi, Shashi Kant Mishra, Pankaj Kumar

Journal of the Operations Research Society of China 2020, 8 (4): 619-636. DOI: 10.1007/s40305-019-00263-y

摘要（331）

PDF

In this paper, we consider semi-infinite mathematical programming problems with equilibrium constraints (SIMPPEC). By using the notion of convexificators, we establish sufficient optimality conditions for the SIMPPEC. We formulate Wolfe and Mond–Weir-type dual models for the SIMPPEC under the invexity and generalized invexity assumptions. Weak and strong duality theorems are established to relate the SIMPPEC and two dual programs in the framework of convexificators.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

13. Forecasting Daily Electric Load by Applying Artificial Neural Network with Fourier Transformation and Principal Component Analysis Technique

Yuji Matsuo, Tatsuo Oyama

Journal of the Operations Research Society of China 2020, 8 (4): 655-667. DOI: 10.1007/s40305-019-00282-9

摘要（352）

PDF

In this paper, we propose a hybrid forecasting model (HFM) for the short-term electric loadforecastingusingartificialneuralnetwork(ANN),discreteFouriertransformation (DFT) and principal component analysis (PCA) techniques in order to attain higher prediction accuracy. Firstly, we estimate Fourier coefficients by the DFT for predicting the next-day load curve with an ANN and obtain approximate load curves by applying the inverse discrete Fourier transformation. Approximate curves, together with other input variables, are given to the ANN to predict the next-day hourly load curves. Furthermore, we predict PCA scores to obtain approximate load curves in the first step, which are then given to the ANN again in the second step. Both DFT and PCA models use input variables such as calendrical and meteorological data as well as past electric loads. Applying those models for forecasting hourly electric load in the metropolitan area of Japan for January and May in 2018, we train our models using historical data since January 2008. The forecast results show that the HFM consisting of “ANN with DFT” and “ANN with PCA” predicts next-day hourly loads more accurately than the conventional three-layered ANN approach. Their corresponding mean average absolute errors show 2.7% for ANN with DFT, 2.6% for ANN with PCA and 3.0% for the conventional ANN approach. We also find that in May, when electric demand is smaller with smaller fluctuations, forecasting errors are much smaller than January for all the models. Thus, we can conclude that the HFM would contribute to attaining significantly higher forecasting accuracy.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

14. Network-Based Multiple UAVs Search Planning for Disaster Relief

Hozumi Morohosi

Journal of the Operations Research Society of China 2020, 8 (4): 669-679. DOI: 10.1007/s40305-019-00283-8

摘要（346）

PDF

This paper studies the use of multiple unmanned aerial vehicles (UAVs) for searching a victim of disaster. We propose a network-based optimization model for planning the search path of multiple UAVs in a disaster-stricken area and estimating the number of UAVs necessary for search. A heuristic algorithm is devised to solve the optimization model and applied to the problem instances taken from potential hazard areas in Japan. Our computational result shows relatively small number of UAVs is enough to cover the area in most of cases. We also give an investigation on the relation between search area and the number of UAVs necessary for search via regression methods.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

15. A Decision Framework for Automatic Guided Vehicle Routing Problem with Traffic Congestions

Lu Zhen, Yi-Wei Wu, Si Zhang, Qiu-Ji Sun, Qi Yue

Journal of the Operations Research Society of China 2020, 8 (3): 357-373. DOI: 10.1007/s40305-018-0216-4

摘要（522）

PDF

Automatic guided vehicles are widely used in various types of warehouses including the automated container terminals. This paper provides a decision framework for port managers to design and schedule automatic guided vehicle routing plans under timevarying traffic conditions. A large number of computational experiments on a grid graph are conducted to validate the efficiency of the proposed decision framework. We also proposed one efficient queueing rule in automatic guided vehicle routing scheduling. Although the complexity of the problem is high, computational results show that our proposed decision framework can provide high quality solutions within a relatively short computation time.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

16. Optimization of Correspondence Times in Bus Network Zones, Modeling and Resolution by the Multi-agent Approach

Elbaz Hassane, Elhilali Alaoui Ahmed

Journal of the Operations Research Society of China 2020, 8 (3): 415-436. DOI: 10.1007/s40305-020-00307-8

摘要（442）

PDF

Urban transportation, especially bus transportation, is an important sign of development in every city in the world. The average waiting time for passengers at correspondence stations of buses is one of the most important measures of effectiveness of bus transportation. To the best of our knowledge, the studies in the literature are about maximizing the number of synchronizations in those correspondence stations whose objective is to minimize the waiting time in the network. The classical definition of synchronization used in the literature related to a time window. In this work, we introduce a new definition of synchronization of two buses in network zones. Within this context, we present a mathematical formulation of the synchronization bus timetabling problem as a multi-objective program, where we use the new meaning for synchronization of two buses in the network zones. Since the problem is NP-hard, we adapt a multi-agent approach to solve it. Numerical experiments show that after adapting the multi-agent approach using our proposed definition, we obtain high-quality solutions compared to the classical definition.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

17. Flight-Based Congestion Pricing Considering Equilibrium Flights in Airport Airside

Bao-Cheng Zhang

Journal of the Operations Research Society of China 2020, 8 (3): 477-491. DOI: 10.1007/s40305-020-00306-9

摘要（447）

PDF

Most of the previous works ignore the fact that equilibrium flights in self-profit maximization scenario are totally different from that in joint profit (social welfare) maximization scenario and take price difference (flight fare difference) between the two scenarios as congestion price, which is a passenger-based method. Most of all, the function of congestion pricing is to alleviate congestion by making airlines reduce flights at peak time. Therefore, the equilibrium flights under self-profit maximization should be the same as the ones under joint profit maximization after congestion prices are tolled. Flight-based congestion pricing method is provided in our paper. The analysis suggests no role for congestion pricing when total real flight production of all airlines is less than the equilibrium flights under joint profit maximization scenario. Otherwise, congestion tolls should be levied to all airlines. Furthermore, congestion price can be determined by solving the corresponding equations system.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

18. Collaborative Optimization of Dock Door Assignment and Vehicle Scheduling in Cross-Docking

Yue Li, Rui-Yun Tang, Li-Wen MuRong, Qian Sun

Journal of the Operations Research Society of China 2020, 8 (3): 493-514. DOI: 10.1007/s40305-019-00266-9

摘要（462）

PDF

Cross-docking is a logistic strategy that can transport goods directly from suppliers or manufacturers to retailers or customers. In daily life, the requirements for timeliness of goods distribution have been continuously improved. Cross-docking can realize the rapid transshipment of goods and improve the process efficiency of distribution greatly. Meanwhile, during the cross-docking process, goods are deposited in the temporary storage area, which reduces the storage cost. This paper focuses on the analysis of reasonable vehicle scheduling and dock door allocation problems in cross-docking. The goal is to minimize the working time of cross-docks by the research on this combinatorial optimization problem. This paper proposes the genetic algorithm (GA) and the hybrid particle swarm optimization to solve the three-scale (small, medium and large) cross-docks. Optimal completion time, average completion time and average solution time are considered as factors to evaluate the efficiency of two algorithms on three scales. And then the concept of mixed-mode dock door is introduced. GA is used to conduct numerical experiments with mixed dock doors on different scales. Finally, by comparing the utilization rate of mixed dock doors, we can analyze the influence of mixed dock door on vehicles’ waiting time.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

19. Optimizing Distribution Route of Convenience Vegetable Stores Considering Transit Nodes

Pu Li, Hong-Jie Lan, You-Hua Chen

Journal of the Operations Research Society of China 2020, 8 (3): 515-531. DOI: 10.1007/s40305-020-00319-4

摘要（488）

PDF

Convenience vegetable stores are distributed in various districts of the city, which is difficult to distribute, mainly reflected in the high cost of distribution and transportation. In order to solve this problem, combining with the characteristics of convenience vegetable stores and urban transportation, an optimization model of distribution route considering transit nodes is established. The model takes into account both soft time window and hard time window. Soft time window is used to calculate the cost increase caused by an urban traffic jam. Hard time window is the unified service time of convenience vegetable stores, and the cost of transit damage is considered to make the model more realistic. The genetic algorithm is used to solve the model with a onestage solution method. The effectiveness and feasibility of the model and algorithm are verified by an example. The effectiveness of the proposed algorithm is verified by comparing the optimal solutions in the case of setting up transit and not setting up transit. The result shows that when the number of convenience vegetable stores is large, the establishment of transit can reduce the overall transportation cost. Quantitative analysis shows that with the further increase in convenience vegetable stores in cities, the distribution of convenience vegetable stores can be improved by planning scientific path and by increasing transit nodes.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

Select

20. Trade Credit Policy Between Supplier-Manufacturer-Retailer for Ameliorating/Deteriorating Items

Vandana Rai

Journal of the Operations Research Society of China 2020, 8 (1): 79-103. DOI: 10.1007/s40305-018-0203-9

摘要（447）

PDF

This paper is related to the advancement of the inventory models for ameliorating items and focused on the real-life business situation as with the time the deterioration rate of ameliorating items is increased. In the global world, every supply chain entities as suppliers/manufacturers/retailers want to increase the consumption of their goods without any losses. For this, he/she tries to lure manufacturer/retailers by offering some discounts, i.e. credit period for settling the account. The problem states that the manufacturer purchases the ameliorating items from the supplier, where the supplier offers his/her credit period to settle the account. The manufacturer purchases ameliorating items(like pigs,fishes,ducklings, etc.)and take those items as raw material; when the livestock matures the manufacturer sells it to the retailer and offer credit time for settling the account. Reason to propose the model is when the quantities of livestock become larger, then the manufacturer faces difficulty in maintaining all the livestock. In such a situation, the traditional method (without offering credit period) fails to provide the maximum profit to the manufacturer. Therefore, in order to get maximum profit, the manufacturer needs some more realistic scientific outlook for making decisions. The proposed model provides a more realistic assumption of business markets, by offering credit policy. In the introduced model, manufacturer faces amelioration and deterioration rate simultaneously due to the growth and the death of livestock. The amelioration and deterioration rates are assumed as the Weibull distribution type. Shortages allowed only for the retailer, which is partially backlogged. The main goal of this paper is to minimize the total relevant inventory cost for both the manufacturer and the retailers, by finding the optimal replenishment policy. The mathematical formulation with optimal solutions for manufacturer and retailers are given. Convexity and existence of the proposed model via numerical examples and graphical representations are explained. Finally, the conclusions with some future research direction are discussed.

参考文献 | 相关文章 | 多维度评价 | 评论（0）

专题专辑