Comparison of metaheuristics for the single vehicle pickup and delivery routing problem with multiple commodities
Notice bibliographique
Résumé
The problem that we are going to study in this thesis is an extension of a Vehicle Routing Problem with Pickups and Deliveries -Single Vehicle Pickup and Delivery Problem with Multiple Commodities.In this problem there is only one vehicle that serves customers which have delivery and pickup demands in many commodities.The main objective of the problem is to find the least cost route, provided that pickup and delivery demands of all customers are satisfied.Additionally, the vehicle capacity should not be exceeded for any of the commodities.At present only one method which allows for solving Single Vehicle Pickup and Delivery Problem with Multiple Commodities exists -it is a heuristic by Gjengstrø and Vaksvik (2008).So, there is the possibility for improvements.This thesis presents two new Tabu search based metaheuristics.These metaheuristics are more advanced in comparison to heuristic by Gjengstrø and Vaksvik.Their core concept is changing the neighborhood when the search process sticks in the local optimum and can no longer improve the solution.The first metaheuristic utilizes the idea of Variable Neighborhood Search and changes the neighborhood each time the current solution cannot be improved.The second is more sophisticated -it selects the neighborhood with the probability which is calculated according to the search history.It also uses Simulated annealing technique to accept worse solutions.Computational results show that both metaheuristics are especially good in solving problem instances where the vehicle load is less than 100% of its maximal capacity.It is also shown that changing the load influences shapes of the obtained solutions and the number of visits to customers in the routes.Assumption that optimal solutions have only customers that are visited once is not true.We present situations when Hamiltonian-shaped routes are load-infeasible and the optimal solution then is non-Hamiltonian.Sometimes even if Hamiltonian solutions are feasible the route of the least cost is non-Hamiltonian and thus, it has customers which are visited more than once.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,002 | 0,005 |
| Méta-épidémiologie (sens strict) | 0,002 | 0,001 |
| Méta-épidémiologie (sens large) | 0,002 | 0,003 |
| Bibliométrie | 0,003 | 0,003 |
| Études des sciences et des technologies | 0,001 | 0,000 |
| Communication savante | 0,002 | 0,002 |
| Science ouverte | 0,002 | 0,001 |
| Intégrité de la recherche | 0,002 | 0,002 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,003 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule source (Gemma direct ou Codex distillé), pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».