In the take-out food industry, improper path planning by couriers often leads to low delivery efficiency. Most of the existing VRP research focuses on the optimization of express delivery and other industries, and there is a lack of optimization algorithm research for the food delivery with real-time characteristics. Aiming at the Online to Offline (O2O) take-out delivery routing optimization problem, this paper takes a comprehensive consideration of its dynamic delivery requirements, cargo differentiation and other characteristics as well as constraints such as time windows and cargo capacities, and establishes an O2O dynamic route optimization model of the take-out delivery personnel, in which the business districts are regarded as a delivery centre, and the number of delivery personnel and the total travel time by the delivery personnel are taken as the minimization targets. Using the method of periodically processing new orders, the resultant dynamic adjustment problem of the delivery personnel's route is converted into a series of static TSP sub-problems and thereby a phased heuristic real-time delivery routing optimization algorithm framework is designed, and a concrete algorithm and a numerical example are given. A set of test cases centered on business districts is generated on the basis of a number of widely used VRP instances, the algorithm is tested through simulation experiment and compared with other algorithms. The results show that the algorithm proposed in this paper can make full use of the delivery personnel near the location of the new orders to conduct the delivery, optimize the corresponding delivery route, and effectively reduce the number of delivery personnel for delivery and the total travel time by the delivery personnel.
The $k$-means problem is a very important problem in the field of machine learning and combinatorial optimization. It is a classic NP-hard problem, which is widely used in data mining, business production decision-making, image processing, biomedical technology, and more. As people in these fields pay more and more attention to personal privacy protection, which raises a question: In the case that decisions are usually made by artificial intelligence algorithms, how to ensure that as much information as possible is extracted from the data without revealing personal privacy? In the past ten years, experts and scholars have continuously studied and explored the $k$-means problem with privacy protection, and has also obtained many results with theoretical guiding significance and practical application value. In this paper we mainly introduce these differential privacy algorithms of the $k$-means problem for readers.
Low-rank tensor completion is widely used in data recovery, and the tensor completion model based on tensor train (TT) decomposition works well in color image, video and internet data recovery. This paper proposes a tensor completion model based on the third-order tensor TT decomposition. In this model, the sparse regularization and the spatio-temporal regularization are introduced to characterize the sparsity of the kernel tensor and the inherent block similarity of the data, respectively. According to the structural characteristics of the problem, some auxiliary variables are introduced to convert the original model into a separable form equivalently, and the method of combining proximal alternating minimization (PAM) and alternating direction multiplier method (ADMM) is used to solve the model. Numerical experiments show that the introduction of two regular terms is beneficial to improve the stability and practical effect of data recovery, and the proposed method is superior to other methods. When the sampling rate is low or the image is structurally missing, the presented method is more effective.
We consider the bounded inverse optimal value problem on minimum spanning tree under unit $l_{\infty}$ norm. Given an edge weighted connected undirected network $G=(V, E, w)$, a spanning tree $T^0$, a lower bound vector $\bm{l}$, an upper bound vector $\bm{u}$ and a value $K$, we aim to obtain a new weight vector $\bm{\bar{w}}$ satisfying the lower and upper bounds such that $T^0$ is a minimum spanning tree under the vector $\bm{\bar{w}}$ with weight $K$. The objective is to minimize the modification cost under unit $l_{\infty}$ norm. We present a mathematical model of the problem. After analyzing optimality conditions of the problem, we develop an $O(|V||E|)$ strongly polynomial time algorithm.
As a special abstract convex (concave) sets, radiant sets and co-radiant sets play the important roles in abstract convex analysis and the theory of multiobjective optimization problems. We first establish the equivalent characterizations for the radiant sets and co-radiant sets. Finally, we apply important properties to the characterization of the approximate solutions of the vector optimization problems, and obtain the equivalent characterization of the approximate solution sets.
This paper investigates a non-zero-sum stochastic differential investment and reinsurance game with delay effect between two competitive insurers, who aim to maximize the mean-variance utility of his terminal wealth relative to that of his competitor. By applying stochastic control theory, corresponding extended Hamilton-Jacobi-Bellman (HJB) system of equations are established. Furthermore, closed-form expressions for the Nash equilibrium investment and reinsurance strategies and the corresponding value functions are derived both in the classical risk model and its diffusion approximation. Finally, some numerical examples are conducted to illustrate the influence of model parameters on the equilibrium investment and reinsurance strategies and draw some economic interpretations from these results.
A combined response surface method is presented for expensive black-box global optimization, which can adaptively take sampling points during iterations. Under the framework of response surface method, the convex combination of the cubic radial basis function and the thin plate spline radial basis function is adopted as the response surface. In the initial phase of the algorithm, the global optimizer of the auxiliary function formed by the product of the response surface model and the power of the distance indicator function will be taken as the new sample point. In the following iterations, if the distance between the two response surface models of the two consecutive iterations is smaller than a given threshold, then the global optimizer of the current response surface model will be taken as the next sample point, otherwise the sampling strategy of the initial phase will be adopted. The effectiveness of the proposed algorithm is demonstrated by the results of the numerical experiments carried respectively on 7 standard test problems and 22 standard test problems.
A scaled incremental gradient algorithm for minimizing a sum of continuously differentiable functions is presented. At each iteration of the algorithm, the iterate is updated incrementally by a sequence of some steps, and each step is cyclically evaluates a normalized gradient of a single component function (or several component functions). Under some moderate assumptions, the convergence result of the algorithm employing the divergence step sizes is established. As applications, the new algorithm and the (unscaled) one proposed by Bertsekas D P, Tsitsikils J N are applied to solve the robust estimation problem and the source localization problem, respectively. Some numerical experiments show that the new algorithm is more effective and robust than the corresponding (unscaled) one.
As a feature extraction method, nonnegative tensor factorization has been widely used in image processing and pattern recognition for its advantages of preserving the internal structural features of data and strong interpretability. However, there are two problems in this method: one is that there is unnecessary correlation between the decomposed base images, which leads to more redundant information and takes up a lot of memory; the other is that the coding is not sparse enough, which leads to the expression of the image is not concise enough. These problems will greatly affect the accuracy of face recognition. In order to improve the accuracy of face recognition, a face recognition algorithm based on orthogonal and sparse constrained nonnegative tensor factorization is proposed. Firstly, orthogonal and sparse constraints are added to the traditional nonnegative tensor factorization to reduce the correlation between the base images and obtain sparse coding. Secondly, the original face image and the decomposed base image are used to calculate the low dimensional feature representation of the face. Finally, cosine similarity is used to measure the similarity between low-dimensional features and judge whether two face images represent the same person. Through experiments in AR database and ORL database, it is found that the improved algorithm can achieve better recognition effect.
According to the characteristics of emergency medical facilities, a hierarchical and progressive location method is proposed to reasonably locating them. Firstly, the entropy weight method is used to calculate the weight of factors related to the location problem, and the preliminary location is also carried out. Secondly, a two-level integer programming model is formulated, which considers the service capacity of the facility, and the actual situation of treating and transferring the mild and severe patients under major public health events. Thirdly, according to the characteristics of the proposed model, an improved immune optimization algorithm is designed to effectively solve it. Finally, the location of emergency medical facilities for public health events in Xiaogan City, Hubei Province is studied as a case, and the reasonable location scheme is obtained for it, which verifies the feasibility of the proposed model and algorithm.
In the supply chain, suppliers provide retailers with a compensation mechanism after the price of products is reduced, so as to encourage retailers to order more products. Therefore, we establish a price difference compensation mechanism model between manufacturer and retailer about a two stage sales. Firstly, we analyze results of the Nash equilibrium strategy and Stackelberg equilibrium strategy under the manufacturer to the retailer's price difference compensation mechanism of decision-making behavior. And then we obtain quantitative relationship of the price difference compensation mechanism under the optimal compromise equilibrium strategies. An algorithm of the approximate optimal compromise equilibrium strategy is proposed at a given price difference compensation coefficient. The case study of intelligent products shows that the mechanism of price difference compensation can improve the expected revenue of supply chain and increase the order quantity of retailers. It shows that the mechanism of price difference compensation can effectively improve relationships between suppliers and retailers.
Let $G=(V, A)$ be a digraph with vertex set $V$ and arc set $A$. A set $D_{k}$ of vertices of $G$ is a $k$-tuple dominating set of $G$ if for every vertex $v\in V(G)\setminus D_{k}$, there exists $u_{i}\in D_{k}$ (possibly some vertex $u_{i}=v$) such that arcs $(u_{i},v)\in A(G)$ for $1\leq i\leq k$. The $k$-tuple domination number $\gamma_{\times k}(G)$ of $G$ is the cardinality of a minimum $k$-tuple dominating set of $G$. In this paper we present a new upper bound on the $k$-tuple domination number of generalized de Bruijn digraphs $G_B(n,d)$. Furthermore, the method of constructing a $k$-tuple dominating set of generalized de Bruijn digraph is given. %which improves the known upper bound in previous literature. For special generalized de Bruijn digraphs, we further improve the bounds on $k$-tuple domination number by directly constructing $k$-tuple dominating sets.
The multiple-sets split equality problem is an extended split feasibility problem, which has a wide application in image reconstruction, language processing, and seismic exploration. In order to solve this problem, we propose a successive relaxed projection algorithm with a variable stepsize which can fully use the information of the current iteration point and does not need the calculation of the operator norm. Furthermore the weak convergence of the algorithm is proved. The numerical examples show the superiority of the algorithm in the number of iterations and the running time.
The two-subgradient extragradient algorithm was proposed by Yair Censor, Aviv Gibali and Simeon Reich for solving the variational inequality problem. A question about the convergence of this algorithm, that is, whether the sequences generated by the algorithm converge to a solution of the variational inequality problem, was raised as an open problem in the paper "Extensions of Korpelevich's extragradient method for the variational inequality problem in Euclidean space" (Optimization, 61(9): 1119-1132, 2012). Our goal in this short remark is to give an answer to this question and give an integrated proof of the full convergence of the algorithm.
Let G be a graph. For two nonnegative integers s and t, an (s, t)-relaxed strong k-edge-coloring is a mapping c : E(G) → [k], such that for any edge e, there are at most s edges adjacent to e and t edges which are distance two apart from e having the color c(e). The (s, t)-relaxed strong chromatic index, denoted by χ' (s, t)(G), is the minimum number k such that G admits an (s, t)-relaxed strong k-edge-coloring. We prove that if G is a graph with mad(G) < 3 and Δ ≤ 4, then χ'(1, 0)(G) ≤ 3Δ. In addition, we prove that if G is a planar graph with Δ ≥ 4 and girth at least 7, then χ'(1, 0)(G) ≤ 3Δ - 1.
In this paper, we investigate a rescheduling problem with rejection on a single machine due to the disruption of job delay. In this problem, we are given a set of jobs that are available at time zero in the planning horizon to be processed on a single machine. Each job has its processing time and weight. Before the formal processing begins, an original schedule according to the shortest weighted processing time first order is given with the goal to minimize the total weighted completion time. Based on the original schedule, the promised due date for each job is also given. However, when the formal processing starts, some jobs are delayed, which creates a disruption to the original schedule. Thus, it is necessary to adjust the original schedule, i.e., rescheduling. To achieve a reasonable service level, we are allowed to reject some delayed jobs by paying the corresponding rejection costs. In the adjusted schedule, the overall objective function is to minimize the sum of the total weighted completion time of the accepted jobs, the total rejection cost of the rejected jobs, and the weighted penalty for the maximum tardiness of the accepted jobs, while keeping the maximum tardiness no more than the given upper bound. For this problem, we design a dynamic programming exact algorithm running in pseudo-polynomial time. Furthermore, we derive a fully polynomial time approximation scheme by using the sparse technique.
With the change of human living environment, public health emergencies occur frequently in recent years. The mutual cooperation between the public and local government is an inevitable choice to deal with the public health emergencies timely and efficiently. Based on the assumption of bounded rationality, this paper discusses the evolution process of the behaviors of the public and local governments, and obtains evolutionarily stable strategies under different conditions. MATLAB is applied for simulation and to analyze how the rewards and the punishments to the public from local governments, the punishments to local governments from the superior departments, and other factors influence the public and local government's strategies. The results in this work show that an effectively promoted mutual cooperation between the public and the government and an active epidemic prevention can be achieved by improving relevant subsidy policies, popularizing epidemic-related laws and regulations, increasing the punishment for violating the epidemic-related rules and regulations, and increasing local government penalties for loosening epidemic prevention.
Based on the PRP conjugate gradient method, we propose an efficient modified PRP conjugate gradient method for solving large-scaled unconstrained optimization problems by using the structure of the CG_DESCENT conjugate gradient method. The proposed method generates a sufficient descent direction at each iteration, which is independent of any line search. Its global convergence and linear convergence rate are established under standard Wolfe line search. The numerical results show that the proposed methods is effective for the given test problems.
A $k$-product facility location problem can be described as follows. There is a set of customers and a set of potential sites where facility can be set up. There are $k$ different products. Each customer needs to be served with all of the $k$ different products and each facility can be set up to provide exact one product. The problem is to select a set of facility to be set up and determine an assignment for each customer to a set of $k$ facilities to provide it with $k$ distinct products. It is assumed that the capacity of any facility is unlimited and there is a non-negative cost for shipping products between each pair of locations. The aim is to minimize the sum of the setup costs and the shipping costs from facilities to customers. For simplicity, we denote the problem by $k$-PUFLP. When the cost of setting up any facility is zero, we denote by $k$-PUFLPN. When $k\geq 3$, the approximation ratio of an existing algorithm is improved to $\frac{3k}{2}-\frac{3}{2}$. When a maximum of $q$ customers are allowed to be unserved, we call it Robust $k$-product facility location problem. For this problem, we addressed an approximation algorithm with an approximate ratio of $\frac{3k}{2}-\frac{3}{2}$. For the Robust $k$-product facility location problem of linear penalties, by considering both outliers and penalty we also designed a $\frac{3k}{2}-\frac{3}{2}$ approximation algorithm.
In this paper, we consider a class of stochastic inverse quadratic second-order cone programming problem. This stochastic model contains complementarity constraints, and is more proper to model some class of real world problems. By employing the techniques of stochastic sampling and smoothing, we construct auxiliary approximate sub-problems to solve the original model. In addition, we proved that if the solutions of the approximate sub-problems converge, then with probability one the limit is the C-stationary point of the original problem. If strict complementarity condition and the second order necessary condition hold, then with probability one the limit is an M-stationary point. A simple numerical test verified the applicability of our approach.
