CN108171387B - Distribution route optimization method and device for interior of building - Google Patents
Distribution route optimization method and device for interior of building Download PDFInfo
- Publication number
- CN108171387B CN108171387B CN201810039882.0A CN201810039882A CN108171387B CN 108171387 B CN108171387 B CN 108171387B CN 201810039882 A CN201810039882 A CN 201810039882A CN 108171387 B CN108171387 B CN 108171387B
- Authority
- CN
- China
- Prior art keywords
- distribution
- building
- personnel
- route
- nodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000005457 optimization Methods 0.000 title claims abstract description 53
- 238000000034 method Methods 0.000 title claims abstract description 30
- 239000011159 matrix material Substances 0.000 claims abstract description 24
- 238000010845 search algorithm Methods 0.000 claims abstract description 12
- 238000010586 diagram Methods 0.000 claims description 27
- 239000007787 solid Substances 0.000 claims description 13
- 239000003086 colorant Substances 0.000 claims description 7
- 238000004364 calculation method Methods 0.000 claims description 5
- 238000005265 energy consumption Methods 0.000 abstract 1
- 238000011960 computer-aided design Methods 0.000 description 6
- 230000008569 process Effects 0.000 description 5
- 230000008901 benefit Effects 0.000 description 3
- 239000000463 material Substances 0.000 description 2
- 230000000007 visual effect Effects 0.000 description 2
- 230000004075 alteration Effects 0.000 description 1
- 235000012745 brilliant blue FCF Nutrition 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
- 238000012360 testing method Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/08—Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
- G06Q10/083—Shipping
Landscapes
- Business, Economics & Management (AREA)
- Engineering & Computer Science (AREA)
- Human Resources & Organizations (AREA)
- Economics (AREA)
- Strategic Management (AREA)
- Marketing (AREA)
- Entrepreneurship & Innovation (AREA)
- Development Economics (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Tourism & Hospitality (AREA)
- Physics & Mathematics (AREA)
- General Business, Economics & Management (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Game Theory and Decision Science (AREA)
- Navigation (AREA)
Abstract
本发明公开了一种面向建筑内部的配送路径优化方法及装置，其中，方法包括：配送时间、配送人员的数量和配送人员的体力消耗分别赋予权重值，且对立体交通网络图设置边权值以生成空间距离系数矩阵、通行时间系数矩阵和体力消耗系数矩阵；获取具有容量约束的模型的约束条件，并且将容量约束转化为目标函数的惩罚项；获取建筑物的配送路径优化模型，并通过两阶段算法和Tabu Search算法求解最优路线，以为配送人员提供当前最优的配送路线。该方法可以在配送人员寻找建筑物内部的配送路线时提供实时的最优方案，有效提高配送效率。
The invention discloses a distribution path optimization method and device facing the interior of a building, wherein the method includes: assigning weight values to distribution time, the number of distribution personnel and the physical energy consumption of the distribution personnel respectively, and setting edge weights for a three-dimensional traffic network graph To generate the spatial distance coefficient matrix, the transit time coefficient matrix and the physical exertion coefficient matrix; obtain the constraints of the model with capacity constraints, and convert the capacity constraints into the penalty terms of the objective function; obtain the distribution route optimization model of the building, and pass The two-stage algorithm and Tabu Search algorithm solve the optimal route to provide the current optimal delivery route for the delivery personnel. The method can provide a real-time optimal solution when the distribution personnel are looking for the distribution route inside the building, and effectively improve the distribution efficiency.
Description
Technical Field
The invention relates to the technical field of path optimization, in particular to a distribution path optimization method and device facing to the interior of a building.
Background
The path optimization system is a relatively important loop in modern logistics distribution systems. Common research and invention are based on urban traffic network and Global Positioning System (GPS) Positioning information, and are oriented to optimization algorithms in outdoor distribution processes.
However, with the rise of the "last mile" distribution, the order is to be delivered to the customer quickly and accurately, which requires not only considering the outdoor distribution process, but also accessing the interior of the building for distribution. In the related art, couriers usually search routes according to building interior signs, and due to the fact that the interior structures of a plurality of high-rise buildings are complex, tools such as elevators can be used in the distribution process, the distribution effect can be directly influenced by an improper routing scheme, and solution is needed.
Disclosure of Invention
The present invention is directed to solving, at least to some extent, one of the technical problems in the related art.
Therefore, an object of the present invention is to provide a method for optimizing a distribution route facing the interior of a building, which can effectively improve distribution efficiency.
Another object of the present invention is to provide a distribution route optimization device facing the interior of a building.
In order to achieve the above object, an embodiment of an aspect of the present invention provides a method for optimizing a distribution path facing an interior of a building, including the following steps: acquiring an internal structure of a building to generate a three-dimensional traffic network map of the building; respectively endowing distribution time, the number of distribution personnel and physical strength consumption of the distribution personnel with weighted values, and setting side weighted values for the three-dimensional traffic network diagram to generate a space distance coefficient matrix, a transit time coefficient matrix and a physical strength consumption coefficient matrix; acquiring constraint conditions of a model with capacity constraints, and converting the capacity constraints into penalty terms of an objective function; and obtaining a distribution path optimization model of the building, and solving an optimal route through a two-stage algorithm and a Tabu Search algorithm to provide a current optimal distribution route for distribution personnel.
According to the building interior-oriented distribution path optimization method, the three-dimensional traffic network diagram can be constructed, the distribution path optimization model of the building is obtained, and the optimal route is solved through the two-stage algorithm and the Tabu Search algorithm, so that the current optimal distribution route is provided for distribution personnel, and the distribution efficiency is effectively improved.
In addition, the distribution path optimization method facing the interior of the building according to the above embodiment of the present invention may further have the following additional technical features:
further, in an embodiment of the present invention, the internal structure is obtained by inputting a CAD (Computer Aided Design) structure diagram of the building into a system model, so as to construct a three-dimensional traffic network diagram of the building.
Further, in one embodiment of the present invention, in the three-dimensional traffic network diagram, each solid node represents a customer location, different colors represent different floors, hollow nodes represent diversions of traffic paths, a connecting line between the nodes represents that a directly arriving traffic path exists between two points, and a connecting edge of a floor represents a traffic path between floors, wherein a solid floor represents a staircase and a dashed floor represents an elevator.
Further, in one embodiment of the present invention, the penalty value function is represented as follows:
wherein C is the number of delivered commodities actually carried by the delivery personnel, CmAnd e is a penalty coefficient for the maximum number of commodities which can be carried by the distribution personnel.
Further, in an embodiment of the present invention, the delivery path optimization model is:
wherein N is the set of all nodes in the network, K is the set of all distribution personnel, i is the node numbered i in the traffic network, j is the node numbered j in the traffic network, K is the distribution personnel numbered K, and xijkFor the kth person passing through i-j road section, yjkWhether the jth customer is delivered for the kth delivery person,
the physical effort to be expended to dispense personnel to move from i to j,
generalized time, x, taken for a dispenser to move from i to jiokWhether the kth delivery person returns to the origin, VfIs a set of virtual nodes in the network and S is any subset of network nodes.
In order to achieve the above object, according to another embodiment of the present invention, an apparatus for optimizing a distribution route facing an interior of a building is provided, including: the system comprises an acquisition module, a display module and a display module, wherein the acquisition module is used for acquiring the internal structure of a building to generate a three-dimensional traffic network map of the building; the generating module is used for respectively endowing distribution time, the number of distribution personnel and physical consumption of the distribution personnel with weighted values, and setting side weighted values for the three-dimensional traffic network map to generate a space distance coefficient matrix, a transit time coefficient matrix and a physical consumption coefficient matrix; the optimization module is used for acquiring constraint conditions of a model with capacity constraint and converting the capacity constraint into a penalty item of an objective function; and the calculation module is used for obtaining the distribution path optimization model of the building and solving the optimal route through a two-stage algorithm and a Tabu Search algorithm so as to provide the current optimal distribution route for distribution personnel.
The distribution path optimization device facing the interior of the building, provided by the embodiment of the invention, can be used for solving the optimal path by constructing the three-dimensional traffic network diagram, acquiring the distribution path optimization model of the building and using the two-stage algorithm and the Tabu Search algorithm so as to provide the current optimal distribution path for distribution personnel and effectively improve the distribution efficiency.
In addition, the distribution path optimization device facing the interior of the building according to the above embodiment of the present invention may further have the following additional technical features:
further, in one embodiment of the invention, the internal structure is obtained by inputting the CAD structure diagram of the building into a system model, so as to construct the three-dimensional traffic network diagram of the building.
Further, in one embodiment of the present invention, in the three-dimensional traffic network diagram, each solid node represents a customer location, different colors represent different floors, hollow nodes represent diversions of traffic paths, a connecting line between the nodes represents that a directly arriving traffic path exists between two points, and a connecting edge of a floor represents a traffic path between floors, wherein a solid floor represents a staircase and a dashed floor represents an elevator.
Further, in one embodiment of the present invention, the penalty value function is represented as follows:
wherein C is the number of delivered commodities actually carried by the delivery personnel, CmAnd e is a penalty coefficient for the maximum number of commodities which can be carried by the distribution personnel.
Further, in an embodiment of the present invention, the delivery path optimization model is:
wherein N is the set of all nodes in the network, K is the set of all distribution personnel, i is the node numbered i in the traffic network, j is the node numbered j in the traffic network, K is the distribution personnel numbered K, and xijkFor the kth person passing through i-j road section, yjkWhether the jth customer is delivered for the kth delivery person,
the physical effort to be expended to dispense personnel to move from i to j,
generalized time, x, taken for a dispenser to move from i to jiokWhether the kth delivery person returns to the origin, VfIs a set of virtual nodes in the network and S is any subset of network nodes.
Additional aspects and advantages of the invention will be set forth in part in the description which follows and, in part, will be obvious from the description, or may be learned by practice of the invention.
Drawings
The foregoing and/or additional aspects and advantages of the present invention will become apparent and readily appreciated from the following description of the embodiments, taken in conjunction with the accompanying drawings of which:
fig. 1 is a flowchart of a distribution path optimization method for the interior of a building according to an embodiment of the present invention;
FIG. 2 is a schematic view of a three-dimensional traffic network inside a building according to one embodiment of the present invention;
FIG. 3 is a diagram of an optimal delivery path indication, according to one embodiment of the present invention;
fig. 4 is a schematic structural diagram of a distribution path optimizing device facing the interior of a building according to an embodiment of the present invention.
Detailed Description
Reference will now be made in detail to embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like or similar reference numerals refer to the same or similar elements or elements having the same or similar function throughout. The embodiments described below with reference to the drawings are illustrative and intended to be illustrative of the invention and are not to be construed as limiting the invention.
The following describes a method and an apparatus for optimizing a distribution path for an interior of a building according to an embodiment of the present invention with reference to the accompanying drawings, and first, a method for optimizing a distribution path for an interior of a building according to an embodiment of the present invention will be described with reference to the accompanying drawings.
Fig. 1 is a flowchart of a distribution route optimization method for the interior of a building according to an embodiment of the present invention.
As shown in fig. 1, the method for optimizing the distribution route facing the interior of the building includes the following steps:
in step S101, the internal configuration of the building is acquired to generate a three-dimensional traffic network map of the building.
Further, in one embodiment of the invention, the internal structure is obtained by inputting the CAD structure diagram of the building into the system model, so as to build the three-dimensional traffic network diagram of the building.
Further, in one embodiment of the present invention, in the three-dimensional traffic network diagram, each solid node represents a customer location, different colors represent different floors, hollow nodes represent diversions of traffic paths, a connecting line between the nodes represents that a directly arriving traffic path exists between two points, and a floor connecting edge represents a traffic path between floors, wherein a solid floor line represents a staircase and a dashed floor line represents an elevator.
For example, as shown in fig. 2, in the embodiment of the present invention, a CAD structure diagram of a building is input into a system model to obtain an internal structure of the building, so as to build a three-dimensional traffic network of the building, where each solid node represents a customer location, and different colors represent different floors (as in fig. 1, blue 1 represents Floor a, and green 2 represents Floor B). Hollow nodes are "virtual nodes" in the network, representing only bifurcations in the traffic path. A line between the nodes indicates that there is a traffic path between the two points that can be reached directly. It should be noted that the red continuous edge, i.e. the floor continuous edge, represents the traffic path between floors, wherein the red solid line 3, i.e. the floor solid line, represents the stairs, and the red dotted line 4, i.e. the floor dotted line (the dotted line indicates that the edge weight thereof is not a definite value) represents the elevator. In actual operation, in order to facilitate operation, the embodiment of the invention can perform dimension reduction operation under the condition of reserving the node floor information.
In step S102, weight values are respectively given to the delivery time, the number of delivery persons, and the physical consumption of the delivery persons, and a side weight value is set for the three-dimensional traffic network map to generate a spatial distance coefficient matrix, a transit time coefficient matrix, and a physical consumption coefficient matrix.
It can be understood that, in the stereo traffic network diagram constructed by the embodiment of the present invention, three optimization objectives can be considered simultaneously by the embodiment of the present invention: the distribution time (T) is shortest, the number (N) of distribution personnel is least, the physical strength (F) of the distribution personnel is least, and weight values a, b and c are respectively given to the distribution personnel, and respectively represent the importance degree of the distribution personnel in the total optimization target.
Because the distribution time and the physical consumption of distribution personnel need to be considered in the objective function, the embodiment of the invention can set three side weights for the connecting sides of the distribution network in the building, and respectively generate three value coefficient matrixes in the objective function: spatial distance coefficient matrix WdThe transit time coefficient matrix WtAnd physical exertion coefficient matrix Wf. Wherein, the space distance is the Euclidean distance between two points; physical power consumption is the physical power that the delivery personnel need consume through this section route, and according to actual conditions, it is less to sit the physical power that the elevator needs to consume, and climbs stair then can consume more physical power relatively.
In addition, the transit time in the side weight is defined as the time required for the distribution personnel to pass through the path, and in the general vehicle path problem, the transit time is directly proportional to the space distance, but in the vertical building distribution problem, the driving speeds are not completely the same for different road sections, for example, even if the Euclidean distance of a certain stair section is the same as that of a certain plane section, the transit time of the stair is obviously longer in practical situations. In addition, for an elevator road section, the passing time is changed with probability, so that the running condition of the elevator in an office building needs to be counted or simulated to obtain the expected passing time.
In step S103, constraints of the model with capacity constraints are obtained, and the capacity constraints are converted into penalty terms of the objective function.
Further, in one embodiment of the present invention, the penalty value function is represented as follows:
wherein C is the number of delivered commodities actually carried by the delivery personnel, CmAnd e is a penalty coefficient for the maximum number of commodities which can be carried by the distribution personnel.
It can be understood that, according to the common constraints and practical situations of vehicle path planning, the main constraints in the stereoscopic traffic network are: (1) ensuring that each customer has one and only one delivery person to deliver; (2) the starting distribution personnel can finally return to the starting point; (3) the number of persons who are delivered has the highest upper limit; (4) the maximum number of customers delivered by each delivery person is fixed.
The embodiment of the invention performs special processing on the last constraint. That is, the constraint is a capacity constraint corresponding to a general vehicle path problem, but in the offline distribution process inside the actual building, it is found that since the distribution items are generally small and the maximum carrying capacity of the distributor is very flexible, if an upper limit is formulated, certain benefits may be lost. Therefore, in the embodiment of the present invention, a penalty coefficient is designed to convert the constraint into a penalty term in the objective function. The specific penalty function is expressed as follows:
wherein C is the number of delivered commodities actually carried by the delivery personnel, CmAnd e is a penalty coefficient for the maximum number of commodities which can be carried by the distribution personnel.
In step S104, a distribution path optimization model of the building is obtained, and an optimal route is solved through a two-stage algorithm and a Tabu Search algorithm, so as to provide a current optimal distribution route for distribution personnel.
It can be understood that the embodiment of the invention can obtain a distribution path optimization model of the building and combine a two-stage algorithm and a Tabu Search algorithm (TS) to solve the optimal route.
Specifically, firstly, it is assumed that all orders can be delivered through a route (it can be understood that a path optimization problem of single delivery personnel in a vertical building is solved by using a Tabu Search algorithm), secondly, the route is split in consideration of certain constraints (for example, the number of commodities carried by the delivery personnel has a certain limit, and the like), the quantity of the delivery personnel and the delivery quantity limit of the delivery personnel are balanced comprehensively (when the quantity of the delivery personnel is large, the commodities which are delivered by each delivery personnel are reduced, and the delivery quantity limit of the delivery personnel can be met more easily, but fixed cost is increased; and vice versa), and finally, a satisfactory delivery scheme is obtained.
The specific algorithm logic and steps are as follows:
the first step is as follows: generating an initial solution and an initial empty tabu table;
the second step is that: judging whether the algorithm is terminated, if so, turning to the sixth step; if not, turning to the next step;
the third step: calculating the neighborhood of the current solution, and selecting a candidate solution from the neighborhood;
the fourth step: judging whether the optimal solution in the current candidate solutions meets the scofflaw principle, if so, re-entering the taboo list, updating the current solution and the current optimal solution, and turning to the second step; if not, turning to the next step;
the fifth step: judging whether the optimal solution in the current candidate solution accords with a tabu principle, if so, judging whether the suboptimal solution in the candidate solution is judged and judging again, and so on; if the solution does not conform to the tabu principle, updating the current solution, entering a tabu table by the solution, and turning to the second step;
and a sixth step: and finishing the algorithm and outputting the optimal solution.
It should be noted that, for the tabu search algorithm, (1) the initial solution, the embodiment of the present invention directly arranges the numbers of the clients by using the encoding method of the solution. Because of the particularity, the initial solution cannot be generated by the common C-W saving method, so the initial solution of the embodiment of the present invention may adopt a method of randomly generating a natural number array, for example, 1-3-5-4-2-1, which represents the distribution sequence of the distributor. It should be further explained that, since the vertical transportation network is not fully connected, Dijkstra algorithm is first applied to solve the shortest path of the generalized distribution cost between each node in the network before encoding. (2) Tabu watch and tabu watch length. The embodiment of the invention can adopt the 2-Opt method to generate the neighborhood solution, so that the taboo objects in the taboo list are two nodes of the 2-Opt. The length of the tabu table is a numerical value related to the scale of solution and needs to be adjusted in a specific test. (3) And (4) terminating the conditions. The termination condition of the embodiment of the invention is that the operation times reach the maximum iteration times, or the optimal solution is not changed for a long time.
As shown in fig. 3, after the optimal solution is solved, the server system visually displays the optimal delivery solution on the handheld terminal (e.g., mobile phone, iPad, etc.) of the delivery personnel.
In an embodiment of the present invention, the distribution path optimization model is:
wherein N is the set of all nodes in the network, K is the set of all distribution personnel, i is the node numbered i in the traffic network, j is the node numbered j in the traffic network, K is the distribution personnel numbered K, and xijkFor the kth person passing through i-j road section, yjkWhether the jth customer is delivered for the kth delivery person,
the physical effort to be expended to dispense personnel to move from i to j,
generalized time, x, taken for a dispenser to move from i to jiokWhether the kth delivery person returns to the origin, VfIs a set of virtual nodes in the network and S is any subset of network nodes.
It can be understood that, in the embodiment of the present invention, a distribution path optimization model of a building may be obtained, and an optimal route is solved through a two-stage algorithm and a Tabu Search algorithm to provide a current optimal distribution route for distribution personnel, where a mathematical expression of the distribution path optimization model inside the building is as follows:
where N is the set of all nodes in the network,k is the set of all the distribution personnel, i is the node numbered i in the traffic network, j is the node numbered j in the traffic network, K is the distribution personnel numbered K, xijkFor the kth person passing through i-j road section, yjkWhether the jth customer is delivered for the kth delivery person,
the physical effort to be expended to dispense personnel to move from i to j,
generalized time, x, taken for a dispenser to move from i to jiokWhether the kth delivery person returns to the origin, VfIs a set of virtual nodes in the network and S is any subset of network nodes.
In summary, the embodiment of the invention can finally provide the optimal distribution route for the distribution personnel in real time by combining the hardware such as the sensors inside the building, the mobile phone terminals carried by the distribution personnel, the background server and the like, and the software such as the path optimization algorithm inside the building. The in-building distribution system acquires the real-time position information of distribution personnel through a position sensor in a building and outdoor GPS signal positioning, and sends the optimal distribution path to the handheld terminal of the distribution personnel through the calculation of a path planning algorithm of a background server to guide the distribution process of the distribution personnel.
According to the distribution path optimization method facing the interior of the building, which is provided by the embodiment of the invention, the internal structure of the building and the positioning information of distribution personnel can be collected in real time to find out the optimal path, and the optimal path is recommended to the handheld terminal of the distribution personnel in a visual mode, so that the situation of path finding failure caused by strange road conditions is reduced, the distribution time is greatly shortened, the physical consumption of the distribution personnel can be reduced as much as possible through the optimization of the optimal distribution path, and the operation cost is reduced.
Next, a distribution route optimization apparatus for the interior of a building according to an embodiment of the present invention will be described with reference to the accompanying drawings.
Fig. 4 is a schematic structural diagram of a distribution path optimizing device facing the interior of a building according to an embodiment of the present invention.
As shown in fig. 4, the distribution route optimization device 10 facing the interior of the building includes: an acquisition module 100, a generation module 200, an optimization module 300, and a calculation module 400.
The obtaining module 100 is used for obtaining the internal structure of the building to generate a three-dimensional traffic network map of the building. The generating module 200 is configured to assign weighted values to the distribution time, the number of distribution staff, and the physical consumption of the distribution staff, and set a side weighted value to the three-dimensional traffic network map to generate a spatial distance coefficient matrix, a transit time coefficient matrix, and a physical consumption coefficient matrix. The optimization module 300 is used for obtaining the constraint conditions of the model with the capacity constraint and converting the capacity constraint into the penalty term of the objective function. The calculation module 400 is configured to obtain a distribution path optimization model of the building, and solve an optimal route through a two-stage algorithm and a Tabu Search algorithm to provide a current optimal distribution route for distribution personnel. The device 10 of the embodiment of the invention can provide a real-time optimal scheme when the distribution personnel search the distribution route in the building, thereby effectively improving the distribution efficiency.
Further, in one embodiment of the invention, the internal structure is obtained by inputting the CAD structure diagram of the building into the system model, so as to build the three-dimensional traffic network diagram of the building.
Further, in one embodiment of the present invention, in the three-dimensional traffic network diagram, each solid node represents a customer location, different colors represent different floors, hollow nodes represent diversions of traffic paths, a connecting line between the nodes represents that a directly arriving traffic path exists between two points, and a floor connecting edge represents a traffic path between floors, wherein a solid floor line represents a staircase and a dashed floor line represents an elevator.
Further, in one embodiment of the present invention, the penalty value function is represented as follows:
wherein C is the number of delivered commodities actually carried by the delivery personnel, CmAnd e is a penalty coefficient for the maximum number of commodities which can be carried by the distribution personnel.
Further, in an embodiment of the present invention, the delivery path optimization model is:
wherein N is the set of all nodes in the network, K is the set of all distribution personnel, i is the node numbered i in the traffic network, j is the node numbered j in the traffic network, K is the distribution personnel numbered K, and xijkFor the kth person passing through i-j road section, yjkWhether the jth customer is delivered for the kth delivery person, wfijPhysical effort to dispense personnel to move from i to j, wtijGeneralized time, x, taken for a dispenser to move from i to jiokWhether the kth delivery person returns to the origin, VfIs a set of virtual nodes in the network and S is any subset of network nodes.
It should be noted that the foregoing explanation of the embodiment of the method for optimizing a distribution path facing the interior of a building is also applicable to the apparatus for optimizing a distribution path facing the interior of a building of this embodiment, and will not be described herein again.
According to the distribution path optimization device facing the interior of the building, which is provided by the embodiment of the invention, the positioning information of the internal structure of the building and distribution personnel can be collected in real time to find out the optimal path, and the optimal path is recommended to the handheld terminal of the distribution personnel in a visual mode, so that the situation of path finding failure caused by strange road conditions is reduced, the distribution time is greatly shortened, the physical consumption of the distribution personnel can be reduced as much as possible through the optimization of the optimal distribution path, and the operation cost is reduced.
In the description of the present invention, it is to be understood that the terms "central," "longitudinal," "lateral," "length," "width," "thickness," "upper," "lower," "front," "rear," "left," "right," "vertical," "horizontal," "top," "bottom," "inner," "outer," "clockwise," "counterclockwise," "axial," "radial," "circumferential," and the like are used in the orientations and positional relationships indicated in the drawings for convenience in describing the invention and to simplify the description, and are not intended to indicate or imply that the referenced devices or elements must have a particular orientation, be constructed and operated in a particular orientation, and are therefore not to be considered limiting of the invention.
Furthermore, the terms "first", "second" and "first" are used for descriptive purposes only and are not to be construed as indicating or implying relative importance or implicitly indicating the number of technical features indicated. Thus, a feature defined as "first" or "second" may explicitly or implicitly include at least one such feature. In the description of the present invention, "a plurality" means at least two, e.g., two, three, etc., unless specifically limited otherwise.
In the present invention, unless otherwise expressly stated or limited, the terms "mounted," "connected," "secured," and the like are to be construed broadly and can, for example, be fixedly connected, detachably connected, or integrally formed; can be mechanically or electrically connected; they may be directly connected or indirectly connected through intervening media, or they may be connected internally or in any other suitable relationship, unless expressly stated otherwise. The specific meanings of the above terms in the present invention can be understood by those skilled in the art according to specific situations.
In the present invention, unless otherwise expressly stated or limited, the first feature "on" or "under" the second feature may be directly contacting the first and second features or indirectly contacting the first and second features through an intermediate. Also, a first feature "on," "over," and "above" a second feature may be directly or diagonally above the second feature, or may simply indicate that the first feature is at a higher level than the second feature. A first feature being "under," "below," and "beneath" a second feature may be directly under or obliquely under the first feature, or may simply mean that the first feature is at a lesser elevation than the second feature.
In the description herein, references to the description of the term "one embodiment," "some embodiments," "an example," "a specific example," or "some examples," etc., mean that a particular feature, structure, material, or characteristic described in connection with the embodiment or example is included in at least one embodiment or example of the invention. In this specification, the schematic representations of the terms used above are not necessarily intended to refer to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, various embodiments or examples and features of different embodiments or examples described in this specification can be combined and combined by one skilled in the art without contradiction.
Although embodiments of the present invention have been shown and described above, it is understood that the above embodiments are exemplary and should not be construed as limiting the present invention, and that variations, modifications, substitutions and alterations can be made to the above embodiments by those of ordinary skill in the art within the scope of the present invention.
Claims (8)
1. A distribution path optimization method facing the interior of a building is characterized by comprising the following steps:
acquiring an internal structure of a building to generate a three-dimensional traffic network map of the building;
respectively endowing distribution time, the number of distribution personnel and physical strength consumption of the distribution personnel with weighted values, and setting side weighted values for the three-dimensional traffic network diagram to generate a space distance coefficient matrix, a transit time coefficient matrix and a physical strength consumption coefficient matrix;
acquiring constraint conditions of a model with capacity constraints, and converting the capacity constraints into penalty terms of an objective function; and
obtaining a distribution path optimization model of the building, and solving an optimal route through a two-stage algorithm and a Tabu Search algorithm to provide a current optimal distribution route for distribution personnel;
the distribution path optimization model is as follows:
wherein N is the set of all nodes in the network, K is the set of all distribution personnel, i is the node numbered i in the traffic network, j is the node numbered j in the traffic network, K is the distribution personnel numbered K, and xijkFor the kth person passing through i-j road section, yjkWhether the jth customer is delivered for the kth delivery person,
the physical effort to be expended to dispense personnel to move from i to j,
generalized time, x, taken for a dispenser to move from i to jiokWhether the kth delivery person returns to the origin, VfIs a set of virtual nodes in the network and S is any subset of network nodes.
2. The building interior-oriented distribution path optimization method according to claim 1, wherein the interior structure is obtained by inputting a CAD structural diagram of the building into a system model so as to build a three-dimensional traffic network diagram of the building.
3. The building interior-oriented delivery route optimization method according to claim 2, wherein in the three-dimensional traffic network diagram, each solid node represents a customer location, different colors represent different floors, hollow nodes represent branches of the traffic route, a connecting line between the nodes represents a traffic route in which direct arrival exists between two points, and a connecting edge of a floor represents a traffic route between floors, wherein a solid floor line represents a staircase and a dashed floor line represents an elevator.
4. The building interior-oriented distribution path optimization method according to claim 1, wherein the penalty value function is expressed as follows:
wherein C is the number of delivered commodities actually carried by the delivery personnel, CmAnd e is a penalty coefficient for the maximum number of commodities which can be carried by the distribution personnel.
5. A building interior-facing distribution path optimizing device, comprising:
the system comprises an acquisition module, a display module and a display module, wherein the acquisition module is used for acquiring the internal structure of a building to generate a three-dimensional traffic network map of the building;
the generating module is used for respectively endowing distribution time, the number of distribution personnel and physical consumption of the distribution personnel with weighted values, and setting side weighted values for the three-dimensional traffic network map to generate a space distance coefficient matrix, a transit time coefficient matrix and a physical consumption coefficient matrix;
the optimization module is used for acquiring constraint conditions of a model with capacity constraint and converting the capacity constraint into a penalty item of an objective function; and
the calculation module is used for obtaining a distribution path optimization model of the building, solving an optimal route through a two-stage algorithm and a Tabusearch algorithm, and providing a current optimal distribution route for distribution personnel;
the distribution path optimization model is as follows:
wherein N is the set of all nodes in the network, K is the set of all distribution personnel, i is the node numbered i in the traffic network, j is the node numbered j in the traffic network, K is the distribution personnel numbered K, and xijkFor the kth person passing through i-j road section, yjkWhether the jth customer is delivered for the kth delivery person,
the physical effort to be expended to dispense personnel to move from i to j,
generalized time, x, taken for a dispenser to move from i to jiokWhether the kth delivery person returns to the origin, VfIs a set of virtual nodes in the network and S is any subset of network nodes.
6. The building interior-oriented distribution path optimization device according to claim 5, wherein the interior structure is obtained by inputting a CAD structural diagram of the building into a system model so as to build a three-dimensional traffic network diagram of the building.
7. The building interior-oriented delivery route optimization device according to claim 6, wherein in the three-dimensional traffic network diagram, each solid node represents a customer location, different colors represent different floors, hollow nodes represent branches of the traffic route, a connecting line between the nodes represents a traffic route in which direct arrival exists between two points, and a connecting side of the floors represents a traffic route between floors, wherein a solid floor line represents a staircase and a dashed floor line represents an elevator.
8. The building interior-oriented distribution path optimization device according to claim 5, wherein the penalty value function is expressed as follows:
wherein C is the number of delivered commodities actually carried by the delivery personnel, CmAnd e is a penalty coefficient for the maximum number of commodities which can be carried by the distribution personnel.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810039882.0A CN108171387B (en) | 2018-01-16 | 2018-01-16 | Distribution route optimization method and device for interior of building |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810039882.0A CN108171387B (en) | 2018-01-16 | 2018-01-16 | Distribution route optimization method and device for interior of building |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN108171387A CN108171387A (en) | 2018-06-15 |
| CN108171387B true CN108171387B (en) | 2021-01-22 |
Family
ID=62514909
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810039882.0A Active CN108171387B (en) | 2018-01-16 | 2018-01-16 | Distribution route optimization method and device for interior of building |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108171387B (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109711769B (en) * | 2018-12-06 | 2023-10-24 | 遵义汇峰智能系统有限责任公司 | Intelligent monitoring system for community |
| CN111598324A (en) * | 2020-05-11 | 2020-08-28 | 上海东普信息科技有限公司 | Loading vehicle line optimization method, device, equipment and storage medium |
| CN111754051B (en) * | 2020-07-23 | 2021-01-08 | 拉扎斯网络科技（上海）有限公司 | Traffic duration prediction processing method and device |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103413209A (en) * | 2013-07-17 | 2013-11-27 | 西南交通大学 | Method for selecting multi-user and multi-warehouse logistics distribution path |
| CN104992242A (en) * | 2015-07-01 | 2015-10-21 | 广东工业大学 | Method for solving logistic transport vehicle routing problem with soft time windows |
| CN107506846A (en) * | 2017-07-10 | 2017-12-22 | 北京石油化工学院 | A kind of vehicle dispatching method and device based on multi-objective particle |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11803926B2 (en) * | 2015-12-10 | 2023-10-31 | Kyndryl, Inc. | Workload distribution optimizer |
-
2018
- 2018-01-16 CN CN201810039882.0A patent/CN108171387B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103413209A (en) * | 2013-07-17 | 2013-11-27 | 西南交通大学 | Method for selecting multi-user and multi-warehouse logistics distribution path |
| CN104992242A (en) * | 2015-07-01 | 2015-10-21 | 广东工业大学 | Method for solving logistic transport vehicle routing problem with soft time windows |
| CN107506846A (en) * | 2017-07-10 | 2017-12-22 | 北京石油化工学院 | A kind of vehicle dispatching method and device based on multi-objective particle |
Non-Patent Citations (2)
| Title |
|---|
| 基于动态交通网络的城市物流配送路径优化研究.;李波;《中国优秀硕士学位论文全文数据库 经济与管理科学辑》;20170715(第7期);第J145-103页 * |
| 带容量约束车辆路由问题的改进蚁群算法;王沛栋;《控制与决策》;20121130;第27卷(第11期);第1633-1643页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN108171387A (en) | 2018-06-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8768614B2 (en) | Increasing throughput for carpool assignment matching | |
| US9743239B1 (en) | Determining routing points and delivery points | |
| CN108171387B (en) | Distribution route optimization method and device for interior of building | |
| US8630958B2 (en) | Systems and methods for multi-vehicle resource allocation and routing solutions | |
| US20190113356A1 (en) | Automatic discovery of optimal routes for flying cars and drones | |
| US20080172172A1 (en) | Route planning process | |
| CN103267526A (en) | Indoor navigation method and system | |
| CN110861104B (en) | Method, medium, terminal and device for assisting robot in conveying articles | |
| US10438137B2 (en) | System for real-time optimal matching of ride sharing requests | |
| US20210117874A1 (en) | System for dispatching a driver | |
| CN108663047A (en) | A kind of cross-layer paths planning method | |
| CN111784018A (en) | Resource scheduling method and device, electronic equipment and storage medium | |
| CN107704942B (en) | Distribution path determining method, device and equipment | |
| CN107749020A (en) | A kind of commending system based on supposition cab-getter's trip purpose | |
| Silva et al. | A mixed load solution for the rural school bus routing problem | |
| Roghanian et al. | The combination of TOPSIS method and Dijkstra’s algorithm in multi-attribute routing | |
| CN114742507A (en) | Vehicle cargo stowage method, device, computer equipment and storage medium | |
| CN113762598A (en) | A path planning method for emergency evacuation vehicles in comprehensive transportation hubs | |
| CN111476389A (en) | Method and device for pre-estimating order receiving waiting time | |
| CN105719118B (en) | Multi-objective logistics scheduling method and system based on graph theory | |
| Hangli et al. | Precaelevator: Towards zero-waiting time on calling elevator by utilizing context aware platform in smart building | |
| KR100798658B1 (en) | Optimal Pedestrian Path Estimation Algorithm in Future Residential Complex | |
| CN112819394B (en) | Waybill processing method and device, computer-readable storage medium and electronic equipment | |
| Kuusinen et al. | The effect of randomization on constraint based estimation of elevator trip origin-destination matrices | |
| CN115795165A (en) | Air-rail joint whole-process personalized travel scheme recommendation method and device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| OL01 | Intention to license declared | ||
| OL01 | Intention to license declared |