共查询到19条相似文献,搜索用时 46 毫秒
1.
多重运输调度问题的计算复杂性 总被引:2,自引:0,他引:2
本文研究了多重运输调度问题的计算复杂性。分别证明了在平面图上一台车辆的MVRP问题为NP-完全的、在树形网络上求MVRP最小总距离及最小车辆数问题是NP-完全的、MVRP最小总距离和最小车辆数的ε-近似解为NP-完全的。 相似文献
2.
随着绿色制造的到来,在调度问题中考虑能源消耗相关的目标变得至关重要,这已经成为了当下热点研究领域。因此,本文建立以最小化最大完工时间、机器总负荷和总能量消耗为目标的柔性作业车间调度数学模型。就回溯搜索算法的缺点提出改进,该算法通过结合改变个体搜索幅度因子对变异操作进行动态控制,防止种群迭代过程中陷入局部最优,然后通过结合个体引导与随机数扰乱提出一种新的交叉算子,提高后期寻优能力,防止了算法过早收敛。最后,运用基准算例对该算法的求解性进行了验证,并与文献中其他算法从求解精度、求解多样性、求解最优值等方面进行对比,结果表明该改进算法具有优越的求解性能。最后为该问题后续研究提供了三个可行方向:考虑更多约束条件、增加局部搜索算子和考虑实例分析。 相似文献
3.
4.
产销平衡运输问题的表上作业法解法的一个注记 总被引:1,自引:0,他引:1
本文给出了用表上作业法求解产销平衡运输问题当出现退化时在相应空格填“O”的更为明确的规则,利用该规则可以避免可能存在的多余计算。本文还给出了用改进后的表上作业法求解指派问题的方法和步骤,该方法与求解指派问题的常用方法“匈牙利法”相比,具有手工计算更为简便的优点。 相似文献
5.
运输问题表上作业法的一点注记 总被引:3,自引:0,他引:3
表上作业法是运输问题的经典算法,然而按照表上作业法闭回路构建方法有时竟然不能成功,为此本文重新设计了新的闭回路构建方法,改进了表上作业法. 相似文献
6.
7.
考虑多机器生产环境下,研究在加工空档期允许关闭机器的可持续调度问题。同时对工件的指派、工件的开始加工时刻和机器在空档期是否开关机进行决策,以最小化碳排放为目标建立数学规划模型。设计了禁忌搜索混合算法求解模型,首先通过一个企业案例验证了模型和算法的有效性,然后通过仿真算例分析了算法的效率。计算结果表明,可持续调度方式在机器调度层面为企业减少了大量的碳排放。 相似文献
8.
作业车间调度是一类求解困难的组合优化问题,本文在考虑遗传算法早熟收敛问题和禁忌搜索法自适应优点的基础上,将遗传算法和禁忌搜索法相结合,提出了一种基于遗传和禁忌搜索的混合算法,并用实例对该算法进行了仿真研究.结果表明,该算法有很好的收敛精度,是可行的,与传统的算法相比较,有明显的优越性. 相似文献
9.
首先给出了运输问题最优解的相关概念,将最优解扩展到广义范畴,提出狭义多重最优解和广义多重最优解的概念及其区别.然后给出了惟一最优解、多重最优解、广义有限多重最优解、广义无限多重最优解的判定定理及其证明过程.最后推导出了狭义有限多重最优解个数下限和广义有限多重最优解个数上限的计算公式,并举例验证了结论的正确性. 相似文献
10.
本文源自2019年全国大学生数学建模竞赛A题,以质量守恒原理为基础,建立高压油管压力控制优化模型.首先,采用多重搜索算法和微元法,得到密度与压力的递推公式,通过迭代,求出高压油管的压力控制策略;随后,探讨了两个以上的喷油嘴在工作时高压油管内压力波动情况,得出凸轮角速度与喷油嘴的个数大致呈正比关系的结论,且在一定的凸轮角速度下,随着喷油嘴个数的增多,高压油管内的压力稳定性得到一定的提高. 相似文献
11.
12.
Path relinking for the vehicle routing problem 总被引:3,自引:0,他引:3
This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search
method that explores the solution space more thoroughly than other local search based methods by overcoming local optima.
Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect
previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu
search on the vehicle routing problem. 相似文献
13.
14.
15.
Designing delivery districts for the vehicle routing problem with stochastic demands 总被引:4,自引:0,他引:4
Dag Haugland Sin C. Ho Gilbert Laporte 《European Journal of Operational Research》2007,180(3):997-1010
This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart. 相似文献
16.
This paper describes a tabu search heuristic for a vehicle routing problem where the owner of a private fleet can either visit a customer with one of his vehicles or assign the customer to a common carrier. The owner’s objective is to minimize the variable and fixed costs for operating his fleet plus the total costs charged by the common carrier. The proposed tabu search is shown to outperform the best approach reported in the literature on 34 benchmark instances with a homogeneous fleet. 相似文献
17.
A tabu search heuristic for the dynamic transportation of patients between care units 总被引:1,自引:0,他引:1
The problem studied in this paper stems from a real application to the transportation of patients in the Hospital Complex of Tours (France). The ambulance central station of the Hospital Complex has to plan the transportation demands between care units which require a vehicle. Some demands are known in advance and the others arise dynamically. Each demand requires a specific type of vehicle and a vehicle can transport only one person at a time. The demands can be subcontracted to a private company which implies high cost. Moreover, transportations are subject to particular constraints, among them priority of urgent demands, disinfection of a vehicle after the transportation of a patient with contagious disease and respect of the type of vehicle needed. These characteristics involve a distinction between the vehicles and the crews during the modeling phase. We propose a modeling for solving this difficult problem and a tabu search algorithm inspired by Gendreau et al. (1999). This method supports an adaptive memory and a tabu search procedure. Computational experiments on a real-life instance and on randomly generated instances show that the method can provide high-quality solutions for this dynamic problem with a short computation time. 相似文献
18.
The Real Time Vehicle Routing Problem RTVRP is a dynamic routing problem where requests are generated dynamically during the
operation horizon without any previous knowledge. Received requests need to be answered as fast as possible and then assigned
to a vehicle to be served. Due to timing constraints of the RTVRP, a solving approach should give the best compromise between
the cost of the provided solution and the computation time needed to find it. In this paper, we present a neural-tabu search
solving scheme for the RTVRP. The developed approach is composed by two phases; The first part consists of learning and reproducing
previous routing decisions using a feed forward neural network with a particular structure. The second phase is based on a
tabu search heuristic that takes its initial solution from the assignment provided by the neural module. If the reaction time
is still available, the tabu search module will continue ameliorating the final solution. To evaluate the proposed approach
a set of problems are simulated and solved. The obtained results are compared to those given by the First Come First Served
FCFS and Nearest Neighbor NN policies and also to the optimal solutions provided by the GNU Linear Programming Kit GLPK.
相似文献
19.
Arild Hoff Irina Gribkovskaia Gilbert Laporte Arne Løkketangen 《European Journal of Operational Research》2009
This paper considers the vehicle routing problem with pickups and deliveries (VRPPD) where the same customer may require both a delivery and a pickup. This is the case, for instance, of breweries that deliver beer or mineral water bottles to a set of customers and collect empty bottles from the same customers. It is possible to relax the customary practice of performing a pickup when delivering at a customer, and postpone the pickup until the vehicle has sufficient free capacity. In the case of breweries, these solutions will often consist of routes in which bottles are first delivered until the vehicle is partly unloaded, then both pickup and delivery are performed at the remaining customers, and finally empty bottles are picked up from the first visited customers. These customers are revisited in reverse order, thus giving rise to lasso shaped solutions. Another possibility is to relax the traditional problem even more and allow customers to be visited twice either in two different routes or at different times on the same route, giving rise to a general solution. This article develops a tabu search algorithm capable of producing lasso solutions. A general solution can be reached by first duplicating each customer and generating a Hamiltonian solution on the extended set of customers. Test results show that while general solutions outperform other solution shapes in term of cost, their computation can be time consuming. The best lasso solution generated within a given time limit is generally better than the best general solution produced with the same computing effort. 相似文献