Table of Content

15 March 2021, Volume 25 Issue 1

Previous Issue    Next Issue

A survey on driver scheduling in public transportation

Yindong SHEN, Zhuang QIAN, Yuanyuan LI

2021, 25(1):  1-16.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.001

Asbtract ( 5033 )   HTML ( 1274019865)   PDF (1480KB) ( 539 )  

Figures and Tables | References | Related Articles | Metrics

Driver scheduling is one of the indispensable core businesses in public transportation system. The driver scheduling problem has attracted much research interests and a large amount of scheduling approaches have been developed since the 1960s. This paper first introduces the driver scheduling problem and its common mathematical model; then, two kinds of solution modes are summarized whilst an overview of driver scheduling approaches are reported; finally, future research trends and directions are suggested.

Nonlinear combinational dynamic transmission rate model and COVID-19 epidemic analysis and prediction in China

Xiaojin XIE, Kangyang LUO, Yi ZHANG, Jianbing JIN, Haixiang LIN, Zhixiang YIN, Guoqiang WANG

2021, 25(1):  17-30.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.002

Asbtract ( 4630 )   HTML ( 17)   PDF (2859KB) ( 465 )  

Figures and Tables | References | Related Articles | Metrics

Due to the difficulty in accurately estimating the basic infectious number $R_0$ and the low accuracy of single model prediction, the traditional epidemic infectious diseases studying is blocked and not widely implemented operationally. To overcome this challenge, this paper proposes a non-linear model with time varying transmission rate based on the support vector regression instead of basic infection number $R_0$. The non-linear model is applied to analyze and predict the COVID-19 outbreak in China. Firstly, the discrete values of the dynamic transmission rate are calculated. Secondly, the polynomial function, exponential function, hyperbolic function and power function are used to fit with the discrete values of the dynamic transmission rate and the corresponding prediction model is rebuilt on basis of the optimal sliding window period $k=3$. Then, on account of the evaluation indexes such as goodness of fitting, the best three prediction models are selected, and the prediction results are nonlinearly combined. Finally, the combined dynamic transmission rate model is used to analyze and predict the COVID-19 epidemic in Hubei province, outside-Hubei provinces, and the whole China. The empirical results show that the combined dynamic transmission rate model is in relatively good agreement with the COVID-19 epidemic data in different regions. The prediction of COVID-19 epidemic infection points in most provinces well reproduce the real situation. The goodness of fitting of the epidemic prediction curves in Hubei province, outside-Hubei provinces and the whole China from February 27, 2020 are 98.53%, 98.06% and 97.98%, respectively.

Optimal dividend strategies for surplus-dependent premiums and surplus-dependent claim arrivals rates: the cases of bounded dividend rates

Xue LIU, Jingwei LI, Guoxin LIU

2021, 25(1):  31-49.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.003

Asbtract ( 1019 )   HTML ( 6)   PDF (676KB) ( 132 )  

References | Related Articles | Metrics

In this paper, we consider the optimal dividend problem with bounded dividend rate for the risk model with surplus-dependent premiums and surplus-dependent claim arrivals. The objective is to maximize the expected cumulative discounted dividends payment up to the time of ruin. Firstly, we prove that the necessary and sufficient condition for a strategy to be a stationary Markov strategy. Using the the theory of measure-valued generators, we derive the associated measure-valued dynamic programming equation (DPE). Finally, we discuss the relationship between the measure-valued DPE and the corresponding quasi-varational inequalities (QVI), and show that the optimal dividend strategy is a stationary Markov strategy with a band structure.

Strongly convergent ball-relaxed CQ algorithm and its application

Hai YU, Wanrong ZHAN

2021, 25(1):  50-60.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.004

Asbtract ( 1087 )   HTML ( 8)   PDF (625KB) ( 133 )  

Figures and Tables | References | Related Articles | Metrics

In order to solve the split feasibility problem, Yu et al. proposed a ballrelaxed CQ algorithm. Since this algorithm only needs to calculate the projection on the closed balls and does not need to calculate the norm of bounded linear operator, it is easy to implement. But the ball-relaxed CQ algorithm only has weak convergence in infinite dimensional Hilbert spaces. Firstly, a strongly convergent ball-relaxed CQ algorithm is constructed. Under weaker conditions, the strong convergence of the algorithm is proved. Secondly, the algorithm is applied to the projection problem on a class of closed convex sets. Finally, numerical experiments verify the effectiveness of the algorithm.

A proximal gradient method for nonsmooth convex optimization problems

Hongwu LI, Min XIE, Rong ZHANG

2021, 25(1):  61-72.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.005

Asbtract ( 1154 )   HTML ( 9)   PDF (1823KB) ( 269 )  

Figures and Tables | References | Related Articles | Metrics

A Proximal Gradient Method based on linesearch (L-PGM) and its convergence for solving the convex optimization problems which objective function is the sum of smooth loss function and non-smooth regular function are studied in this paper. Considering the loss function's gradient is locally Lipschitz continuous in the problems, the R-linear convergence rate of the L-PGM method is proved. Then, focusing on the problems regularized by the sparse group Lasso function, we prove that the error bound holds around the optimal solution set, thus, the linear convergence for solving such problems with the L-PGM method is given. Finally, The preliminary experimental results support our theoretical analysis.

An existence theorem for efficient solutions of symmetric vector quasi-equilibrium problems

Xiuling WANG, Xunhua GONG

2021, 25(1):  73-80.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.006

Asbtract ( 1097 )   HTML ( 6)   PDF (611KB) ( 103 )  

References | Related Articles | Metrics

In this paper, an existence theorem for efficient solutions of symmetric vector quasi-equilibrium problems is established by using a scalarization method. As applications of the scalarization method, we use the scalarization method to obtain existence theorems for efficient solutions of vector variational inequality and vector quasi-variational inequality.

A new filled function and its application in data fitting problems

Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE

2021, 25(1):  81-88.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.007

Asbtract ( 1167 )   HTML ( 7)   PDF (686KB) ( 169 )  

Figures and Tables | References | Related Articles | Metrics

The filled function method is one of the effective methods to solve the global optimization problem. In this paper, a new continuous and differentiable nonparameter filled function is proposed for the unconstrained optimization problem. The related properties of the filled function are proved and the corresponding algorithm is designed. By comparing with the numerical experimental results in previous literature, it is shown that the proposed filled function algorithm is effective and feasible. Then, the proposed filled function method is used to solve the data fitting example of cutting temperature experimental data, compared with the existing least squares method and genetic algorithm, the fitting effect is better.

A new parameterless filled function for global optimization problems

Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU

2021, 25(1):  89-95.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.008

Asbtract ( 1148 )   HTML ( 8)   PDF (647KB) ( 139 )  

Figures and Tables | References | Related Articles | Metrics

Since the filled function algorithm for global optimization problems has been proposed, the selection and adjustment of parameters have always been the factors that restrict the effectiveness of the algorithm. How to select appropriate parameters in the actual calculation process directly affects and determines the operation speed and efficiency. Therefore, constructing a filled function without parameters is extremely important. This paper proposes a new parameterless filled function, and gives the corresponding filled function algorithm.Through numerical experiments and comparison with existing literature, numerical experiments verify the effectiveness of the algorithm.

Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence

Jiaqing YE, Qianzhu CHEN, Haiping HU

2021, 25(1):  96-106.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.009

Asbtract ( 1291 )   HTML ( 7)   PDF (631KB) ( 156 )  

Figures and Tables | References | Related Articles | Metrics

Inspired by the performance estimation problem (PEP) method, this paper optimizes the step size of the first order method of smooth convex minimization that the gradient corresponding to the iteration point satisfies Q-convergence by examining the worst case convergence boundary (i.e. efficiency) of the cost function. This paper introduces a new and effective first-order method called QGM, which has an effective computation form similar to the optimized gradient method (OGM).

Approximation algorithm for min-max cycle cover problem on a mixed graph

Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU

2021, 25(1):  107-113.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.010

Asbtract ( 1285 )   HTML ( 9)   PDF (805KB) ( 297 )  

Figures and Tables | References | Related Articles | Metrics

We consider a min-max cycle cover problem, in which we are given a positive integer k and a mixed weighted graph G=(V, E, A) with vertex set V, edge set E and arc set A. Each edge in E and each arc in A is associated a weight, respectively. The problem is to determine k tours such that the k tours pass through all the arcs in A. The objective is to minimize the weight of the maximum weight tour. The problem is an important combinatorial optimization problem in operations research and computer science. This problem and its variants are widely used in related industries such as express delivery, trash collection, snow removal, etc. For the problem, we propose the first constant-factor approximation algorithm with ratio 37/5 by using binary search and tour splitting techniques.

Squared metric facility location problem with outliers

Jianfeng REN, Xiaoyun TIAN

2021, 25(1):  114-122.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.011

Asbtract ( 1172 )   HTML ( 11)   PDF (1224KB) ( 145 )  

Figures and Tables | References | Related Articles | Metrics

Traditionally, we assume that all the clients to be provided service in the facility location problems. In our study, we explore the case when only a fraction of clients allow to be denied service in the final solution. Indeed, the existence of outliers will not only increase the total cost, but also have an undesirable effect on the service quality of other clients. We consider the squared metric facility location problem with outliers, which is a generalization of the classic uncapacitated facility location problem. Next we will give a detailed description of the problem. Given a set of facilities with open cost and a set of clients with connection costs, we seek a subset of facilities to open and satisfy the demands of clients. The objective is to minimize the sum of total open and connection cost. We utilize the primal-dual scheme to design an approximation algorithm, and prove that the proposed algorithm is a 9-approximation.

Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected

Jing ZHAO, Erfang SHAN, Jiagui ZHAO

2021, 25(1):  123-131.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.012

Asbtract ( 1189 )   HTML ( 6)   PDF (1784KB) ( 122 )  

Figures and Tables | References | Related Articles | Metrics

Let H be a connected hypergraph. The hypergraph H is called maximally edge connected if its edge connectivity is equal to minimum degree. The hypergraph H is super-edge-connected, if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree. In this paper we give simple degree sequence conditions for uniform linear hypergraphs to be maximally edge-connected. Also, we give a sufficient condition for uniform linear hypergraphs to be super-edge-connected. These results generalize previous results on graphs due to Dankelmann and Volkmann(1997), Hellwig and Volkmann(2005) to hypergraphs.

Weakly entire coloring of outerplanar graphs

Min CHEN, Jianmin YANG, Hao ZHANG, Yiting WANG

2021, 25(1):  132-136.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.013

Asbtract ( 1122 )   HTML ( 7)   PDF (632KB) ( 137 )  

Figures and Tables | References | Related Articles | Metrics

Let G=(V, E, F) be a plane graph. If e₁ and e₂ are consecutively adjacent with the same face, then we say that e₁ and e₂ are facially adjacent. A plane graph G is called weakly entire k-colorable if there is a mapping from V ∪ E ∪ F to {1, …, K} such that any facially adjacent edges, adjacent vertices, adjacent faces, and any two incident elements in V ∪ E ∪ F receive distinct colors. The weakly entire chromatic number, denoted χ_vef(G), of G is defined to be the least integer k such that G is weakly entire k-colorable. In 2016, Fabrici et al. conjectured that every connected, loopless, bridgeless plane graph is weakly entire 7-colorable. In this paper, we prove that the conjecture is true for outerplanar graphs. Namely, outerplanar graphs are weakly entire 7-colorable.

A note on quasi k-connected graphs

Xiaoxia LIN

2021, 25(1):  137-140.  doi:10.15960/j.cnki.issn.1007-6093.2021.01.014

Asbtract ( 1019 )   HTML ( 9)   PDF (524KB) ( 101 )  

References | Related Articles | Metrics

Let G be a k-connected graph, and T be a k-vertex-cut of a k-connected graph G. If G-T can be partitioned into subgraphs G₁ and G₂ such that |G₁| ≥ 2, |G₂| ≥ 2, then we call T a nontrivial k-vertex-cut of G. Suppose that G is a (k-1)-connected graph without nontrivial (k-1)-vertex-cut, then we call G a quasi k-connected graph. In this paper, we prove that for any integer k ≥ 5 and t> $ \frac{k}{2}$, if G is a (K₂+tK₁)-free k-connected graph for which d (v)+d (w)≥ $\frac{{3k}}{2} $+t for any pair v, w of distinct vertices of G, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least $\frac{{\left| {V\left( G \right)} \right|}}{2} $ edges of G such that the contraction of every member of the results in a quasi k-connected graph.